# Tag Info

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 ...

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 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 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 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 If$k$is the bitsize of the integers, then you can compute the Max in$O(n k)$time. Basically, the problem is, given$n$,$k$-bit integers$S_i$, find$i,j$such that$S_i \oplus S_j$is maximum. You treat each$S_i$as a binary string (looking at the binary representation), and create a trie out of those strings. This takes$O(nk)$time. Now for each$...

7

If you want to use JavaScript for scientific computing, why not try Node.js? Node is based on Google's V8 engine with some additional functionality for interacting with the file system, writing servers and linking to C and C++ libraries (this is definitely not an exhaustive list). It sports fast execution times and provides an interactive console as well as ...

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 ...

6

There is no absolute value of how much faster a quad-core would be compared to a single-core. As the comments have said, it very much depends on exactly what you are doing whether it will be faster or slower. Even live performance testing may not give a fair answer since it won't model exact runtime behaviour. In any case, if you are looking for a ...

6

The point of the Python scientific libraries is that Python merely acts as a glue code for shuffling around the data between the scientific libraries. Python itself does little of the high performance grind work. Python is a good language for this, as it supports both the procedural and object-oriented paradigms (and functional to a large degree), and one ...

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'...

6

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 ...

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

The only thing you are missing is the importance of the interconnect between cores/processors/racks and the design of the memory system for each processor. I assume you are referring to the most recent top-500 supercomputer list. That list is sorted by Rmax, not Rpeak. Rpeak is a measure of the theoretical maximum number of floating point operations that ...

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

Just an idea: you can use scientific libraries written in Java (I think you'll find a lot of work already available) with Javascript - that has a syntax similar to Java - used only as a wrapping language for: scripting user interaction (re)modeling and standardization of the underlying high level classes/packages/functions ... though I think it would be ...

5

Sorting helps with $\max$ too. A little bit, at least. Clearly, maximum would be reached by $x \oplus \neg x$. So for each $x = \text{sum}_i$ do a binary search for $\neg x$. That's $O(n \log n)$ time, same as sorting, so that remains to be the complexity of the whole procedure.

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

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

Here is why Strilanc's suggestion works for $\min$. Consider your array $\mathrm{sum}$, and suppose the minimum is achieved by $a_p,a_q$, where $p<q$. Either $a_p = a_q$ (in which case $a_p = a_{p+1}$), or $a_p = x0y$, $a_q = x1z$ for some $x,y,z$. Suppose $q > p+1$, and let $a_{p+1} = xbw$. If $b = 0$ then $a_p \oplus a_{p+1} < a_p \oplus a_q$, ...

4

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 ...

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