Questions tagged [performance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
15
votes
2answers
11k views

Performance of microkernel vs monolithic kernel

A microkernel implements all drivers as user-space programs, and implements core features like IPC in the kernel itself. A monolithic kernel, however, implements the drivers as a part of the kernel (e....
11
votes
5answers
763 views

Why is the OS design able to reduce power consumption?

I have read that OSes like Android and iOS are somehow optimised to improve battery life. My understanding is that a CPU executes a certain number of operations in a certain time, so I would think ...
11
votes
4answers
2k views

Why do we have to trade abstraction for speed?

Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier ...
11
votes
2answers
7k views

Fast hashing: combination of different techniques to identify changes in a file?

I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256. However, the files are expected to be ...
10
votes
3answers
2k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
10
votes
1answer
402 views

Why using Hyper-threading can lead to performance degradation

I have read it at various places like this, that Hyper-threading leads to performance degradation. I am unable to get why or how hyper-threading leads to degradation. Why it is so that even when Hyper-...
9
votes
4answers
10k views

A faster, leaner JavaScript for scientific computing: what features should I keep?

Here I'm really interested in lowering barriers to mathematical education. Target: I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-...
8
votes
3answers
3k views

Finding maximum and minimum of consecutive XOR values

Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$. I have tried this ...
8
votes
2answers
396 views

GCD of a pair of products

I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use ...
7
votes
1answer
162 views

Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”: decreased transistor size (...
6
votes
1answer
389 views

Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
6
votes
2answers
1k views

How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
5
votes
2answers
1k views

Variable size and CPU performance

When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want ...
5
votes
1answer
676 views

Bare Metal Operating Systems in High Performance Computing

Few years back, I stumbled across Return Infinity - the OS framework designed around flat, 64bit memory model, with minimal MMU / VM overhead, etc. I'm wondering if there are any public benchmarks or ...
5
votes
1answer
3k views

Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.
5
votes
2answers
16k views

Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36

I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%. But its not clear how we ...
4
votes
2answers
1k views

What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
4
votes
3answers
133 views

Scientifically acceptable method for comparing performance of algorithms

I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the ...
4
votes
2answers
2k views

Theoretical speed gain of quad core vs. single core

I first asked this question at cstheory, but they suggested to ask my question here, so here it goes ... I'm working on my masters thesis and I need to have theoretical value of the (average) speed ...
4
votes
2answers
15k views

Cache effective access time calculation

In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct ...
4
votes
1answer
5k views

Performance of row- vs. column-wise matrix traversal

Scott Meyers describes here that traversing a symmetric matrix row-wise performes significantly better over traversing it column-wise - which is also significantly counter-intuitive. The reasoning ...
4
votes
2answers
748 views

How to avoid column wise access in matrix multiplication?

I know when we access elements in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise. In GPUs with CUDA/OpenCL ...
3
votes
1answer
2k views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
3
votes
2answers
811 views

Why analysis of Aloha protocol uses Poisson distribution?

Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial ...
3
votes
1answer
2k views

Definition of “c-competitive” algorithm

What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?
3
votes
2answers
245 views

Sorting networks hybrid sort

I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 ...
3
votes
2answers
197 views
3
votes
1answer
111 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
3
votes
1answer
94 views

What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...
3
votes
1answer
151 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
3
votes
1answer
287 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
3
votes
1answer
534 views

Best way to merge different trees to single data structure?

I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast ...
2
votes
5answers
709 views

Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
2
votes
3answers
129 views

How can I evaluate an algorithm for a NP-Hard problem?

I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. ) The professor, ...
2
votes
3answers
133 views

Why computer take long time to open huge text files? [closed]

Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be ...
2
votes
1answer
378 views

Do functional algorithms require more memory than imperative algorithms? [closed]

Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example. The imperative approach would as follows: ...
2
votes
1answer
823 views

Why is the throughput (performance) of the Aloha protocol ≈ 0.18?

I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%. But its not clear ...
2
votes
2answers
777 views

Regarding to the speed of supercomputer

There seems to be a sense of competition in creating the fastest computer in the world, and I feel like technically you just have to continue increasing the core number to gain more flops, which is ...
2
votes
1answer
2k views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
2
votes
1answer
370 views

Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
2
votes
1answer
8k views

MIPS rating formula

Could you please help me to understand the mathematics behind MIPS (million instructions per second) rating formula? The formula for MIPS is: $$ \text{MIPS} = \frac{ \text{Instruction count}}{\...
2
votes
1answer
689 views

Tree flattening with layout guarantees

I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the ...
2
votes
1answer
78 views

Doubt on Performance Comparison of Splay Trees

I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their ...
2
votes
2answers
58 views

Minimum words in a string given a dictionary

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
2
votes
1answer
193 views

What is the basic idea behind the usage of TLBs?

I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache. The ...
2
votes
1answer
402 views

Changing Rabin-Karp without modulo to Rabin-Karp with modulo

I am trying to solve a string matching problem using Rabin-karp algorithm. I made use of Horner's method for calculating hash function, but I forgot to use modulo operator. It's like this now. (this ...
2
votes
1answer
1k views

Understanding Amdahl's Law calculation

I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput. Which is a pretty ...
2
votes
1answer
157 views

The theoretical upper bounds for duplicate detection in a set of objects?

I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection. The debate was mostly centered around the specific behavior of C# collections, such ...
2
votes
1answer
88 views

performance between the data structures

I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I ...
2
votes
1answer
78 views

Optimization of Hierarchical Data Propagation

I have a system in existence which works on parent-child model. They share common attributes, as they belong to same class. A parent can enforces certain data on any user selected attribute, and the ...