24

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.


19

Debunking some myths There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a particular set of flawed benchmarks, but cannot rank languages in a vacuum. C code tends to be faster because people who need every inch of performance use C. A ...


15

Common CPUs that go into smartphones, laptops and even desktop PCs have a variable clock rate. When the scheduler detects that it has idle time, it can reduce the clock rate, and increase it again if there are more processes competing for CPU time. CPUs optimized for battery-powered devices tend to be composed of many functional components that each have ...


12

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass? Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines". https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md https://github.com/baskerville/paragraph-breaker https://cs.uwaterloo.ca/~dberry/ATEP/...


11

As is always the answer (or at least the preface) to performance-related questions: know your problem domain, run comparative benchmarks, and remember what premature optimization is. First, no comprehensive benchmarking trials have compared monolithic kernels to current-generation microkernel systems that operate in an equivalent manner. So, while there may ...


10

This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a Turing machine, $T \cdot S = \Omega(...


9

The performance of a computer for most programs cannot be simply derived from the computer's capacity to perform operations (i.e., peak performance). As Shitikanth's answer states, the memory system and other bottlenecks can keep performance below the peak. In addition, processor frequency is not necessarily proportional to processor performance. It is ...


8

There are two sides to your coin: if you want to do it secure, you will need to use a cryptographically secure hash like SHA256 (crypto-hashes are meant to be fast, but tend to be a bit slow due to security constraints), things like CRCs are definitely quicker, but will never be able to offer the same kind of security (especially when we’re talking about . ...


8

It would seem that the answer, as per usual, has something to do with caches. Since hyper-threads utilize the same L1 and L2 caches, one hyper-thread can trash another's caches. In the worst case the threads take turns trashing the other's cache and performance degrades as the caches are re-filled only to be trashed again. Of course, this is likely very ...


8

The difference would be between loading the complete file into memory and reading the file part-by-part as you need each part. If I open a file in some applications I am asking for it to be fully loaded into memory all in one go. If I play a movie file or DVD in most player applications the applications will be structured to just fetch data as it needs it, ...


7

The Return Infinity site you linked claims that BareMetal is an Exokernel. Exokernel was an MIT research project from the mid to late 1990s which is still widely studied. The philosophy behind Exokernels was that they would provide just mechanism and all policy would move to user-level libraries. In later papers they more specifically said that the kernel ...


7

Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in words and behind the scenes set(words) is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses ...


7

In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements. Given a particular input, a particular implementation of timsort may or may not be faster than a particular implementation of merge sort. Timsort is designed to have a maximum overhead over ...


7

Assuming $n$ is a power of $2$, you have: $$ \sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n). $$


6

It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense. Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is ...


6

There is no single answer. The answer depends upon the specific situation you are in. It's not that there is a single scientifically accepted way of evaluating performance. Instead, a paper should be driven by the claims you want to make. First, figure out what claims you want to make about your scheme. Then, figure out what evidence is needed to ...


6

Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of elements. For example I will give very poor hash for letters, just to ilustrate mechanism: 0) $x = 0;$ 1) for each character in string take ascii value, subtract 'a'...


5

I prefer to call Windows NT and Apple's XNU kernel monolithic instead of hybrid. I don't find the classification of hybrid to have much meaning in practice. In fact one of the original engineers of XNU calls it monolithic[1]. On the issue of performance, the only really in-depth comparison of monolithic vs micro I can find is "Extreme High Performance ...


5

This number is reached first by assuming that messages will be produced and sent according to a Poisson process. $$P[(N(t + \tau) - N(t)) = x] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^x }}{{x!}}$$ This means, that the probability of $x$ messages arriving for the given interval $[t, t+\tau]$ where $\lambda$ messages are expected to arrive, is equal to ...


5

In today's standard architectures, the cache uses what is called "spatial-locality". This is the intuitive idea that if you call some cell in the memory, it is likely that you will want to read cells that are "close by". Indeed, this is what happens when you read 1D arrays. Now, consider how a matrix is represented in the memory: a 2D matrix is simply ...


5

I am not sure what you mean by "complexity optimization". A proper way to compare complexities is by considering their ratio, which is defined up to a constant factor. Considering the difference makes no sense, as there is always the invisible constant factor lurking around, invisible but not negligible. However your problem here is that you have several ...


5

The answer will depend on the compiler. As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code." In particular, good compilers will do tail-call elimination. In some cases this can effectively transform the code into a for-loop. Your example looks like a good example of an instance where this could happen. As @...


5

Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored? Yes, it could make your performance worse. Memory, memory bandwidth, cache density are primary concerns. Larger data size can: result in increased cache and ...


5

This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question ...


5

There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance. One of them is parallelism, as you point out. A second technique trading off more transistors for performance is speculation. Often speculative execution of some kind is combined with parallelism, and this kind of performance optimization ...


4

Creating a new language is not necessary. One can write performant numeric computing in JavaScript today, without compilation/transpilation. As a scripting language, JavaScript compares quite favorably to Python and R. For benchmarks, run the language benchmarks in stdlib, which compares performance across a wide-range of APIs. For server-side applications, ...


4

Unlike in the regular ALOHA protocol, where other nodes can send messages that interfere with ours at any time, in the Slotted ALOHA protocol, the only other time a message can be sent to interfere with ours is if it's sent at the exact time ours is sent (since in Slotted ALOHA messages can only be sent at specific intervals, like every 5 seconds for example)...


4

In terms of processor power the main thing the OS can do is to provide APIs that discourage applications from polling. (And also eliminate all polling inside the kernel and device drivers if there was any.) Then the processor can be put into a low power sleep state whenever there is nothing to do. For every device there needs to be a way for the user ...


4

There are plenty of ways to go about dealing with NP-hard problems. Even if you know the asymptotic upper bounds on worst-case runtime (more you usually don't get), you don't have information about the typical case and the precision of your bound. In the absence of exact analyses, all you can do is run the algorithm on a representative sample of inputs ...


Only top voted, non community-wiki answers of a minimum length are eligible