10 ms·
Computer Scientists’ Trivia
- Animats 10y agoShift, add instead of multiply or divide This is usually not worth it on modern superscalar processors, where multiply is fast and pipelined. It's a win mostly on Arduino-class CPUs. If you need more than one operation to replace a multiply, such as an add and shift or a bit operation, the replacement is probably slower. The costly operation in the example is accessing a large 2D array along the non-dense axis. For big enough arrays, that's a cache miss every time.
- yorwba 10y ago> The costly operation in the example is accessing a large 2D array along the non-dense axis. For big enough arrays, that's a cache miss every time. I half-remember hearing about memory-prefetchers smart enough to detect this kind of strided access and fill the cache accordingly.
- mnw21cam 10y agoThen it turns from a cache miss problem to a memory bandwidth problem. If you are only using a small proportion of the cache line in your calculation, then you effectively multiply the data transferred to the CPU.
- andreareina 10y agoThis is precisely the sort of thing you let the compiler worry about. Using godbolt.org I see that a constant multiplication by 30 is compiled to an `imul` in x86-64 (both clang and gcc) and `lsl`, `sub`, `lsl` in ARM64 (gcc).
- legulere 10y agoRegardless if it is worth it or not: Every compiler does such basic peephole optimisations.
- csl 10y agoI think adding sources would not only be polite, but make it easier for interested readers to delve more deeply into the matter. E.g., as in https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832
- 110011 10y agoOops, I made a similar comment before seeing yours. Glad to find someone else peeved enough about it to point it out. It's such a small thing but I don't understand why it has become more or less acceptable here to just blurt something out in a long blog post without any references whatsoever. It might not be malicious necessarily however the standard for technical writing needs to improve.
- delta1 10y agoOT: beautiful choice of colors and fonts for his blog, I was immediately struck by how pleasant it was to read.
- foo101 10y agoI am seriously unable to tell if you are genuinely appreciating the appearance of the blog or sarcastically mocking it.
- petters 10y agoI think most people would not prefer grey on black fixed width. But it did not bother me that much, personally.
- eru 10y agoI usually go for green on black in my terminals.
- majewsky 10y agoI would like to go with green on black just for hacker street-cred, but how does this work with colors? The normal color set seems to be geared towards black/white or white/black as base colors.
- eru 10y agoMacOsX and Linux terminals support green on black themes out of the box. (Otherwise, I would adopt the white on black option.)
- ben0x539 10y agoworked well for me here!
- delta1 10y agoGenuine appreciation :)
- sspiff 10y ago2^10 = Kilo ~ 10^3 2^20 = Mega ~ 10^6 2^30 = Giga ~ 10^9 2^40 = Tera ~ 10^12 This is wrong - power-of-two magnitudes are called kibi-, mebi-, gibi- and tebibytes. Kilo, Mega, Giga and Tera are prefixes used by the SI unit system, and denote powers of ten. The confusion comes from Microsoft using power of two numbers in calculations, but SI power of ten prefixes in labels. A kilobyte is 1000 bytes, not 1024 bytes.
- hultner 10y agoAs I remember it everyone used to do this (at least in the 90s and early 00s). If I recall correctly Apple only switched to power of ten in 10.6 which is quite recently. I suppose Microsoft may be the one causing confusion today as they keep the user facing power of two system alive (?)
- sspiff 10y agoIt's possible that other systems did the same. I think the impact of Microsoft's decision to use this labeling is by far the greatest, though, given the spread and popularity of Windows for the past 25-30 years.
- maggit 10y agoFrom what I found in Wikipedia, the "kibi"-family of prefixes was not defined before 1998. There's a lot of computer history before (and after!) that establishing the use of kilo for 2^10. Calling this wrong outright is historyless. Perhaps instead we could say: This is a funny artifact of history, and it is contrary to the long standing SI-definition of kilo as 10^3. We have since tried correcting that mistake by introducing the prefixes kibi-, mebi-, etc. A better table could say: kibi = 2^10 ~ 10^3 = kilo ...
- ben0x539 10y agoI never hear anyone use the -bi units unless they're trying to be clever, and I'm fairly sure at most storage devices use the power-of-ten units. Am I alone in that?
- tomsmeding 10y ago> To improve the performance, take the redundant multiplication out of the loop like below: Um, that multiplication is already outside the loop. You said before that one shouldn't trust the optimiser, but it did the right thing here... EDIT: (After reading the entire thing) The memory aliasing point completely correct and very important (even though you probably want the `b[i] = val` outside the inner loop...); in C, I'd argue that this point needs even more attention if we're micro-optimising already. The strlen call is only repeated (leading to quadratic behaviour) because the string may be modified in the inner loop. Might be worth mentioning that the calls will be hoisted (i.e. merged to one) if the string is constant and nothing can alias to it. The "replacing multiplication by additions", the replacing multiplication with a shift and the hoisting I mentioned above are all redundant optimisations for a programmer: compilers will trivially do that already. The first two are instances of "strength reduction" and feature in most compilers' -O1 set. Conclusion: I do like the first part about the actual trivia, but I think the micro-optimisation part misses the point somewhat.
- danbruc 10y agoThe memory aliasing point completely correct and very important (even though you probably want the `b[i] = val` outside the inner loop...) [...] Do you mean the assignment to b should be or must be outside of the inner loop? I am pretty sure it must be outside of the inner loop in order to make the assembly version correct.
- tomsmeding 10y agoVery true, didn't spot that one. Then the C code is probably a typo, but still incorrect. :P
- adwn 10y ago> Um, that multiplication is already outside the loop. You said before that one shouldn't trust the optimiser, but it did the right thing here... It's even more ironic given that the author wrote right above that part: "Always profile the program’s performance." If they'd actually followed their own advice, they'd have noticed that performance was not improved through this manual "optimization".
- gumoro 10y agoBeautiful typo about two's complement: > Simply filp all bits and add 1.
- dvirsky 10y agoThere's an error in the Primitive C types section, the width of long: > long 8 (32 bit) 8 (64 bit) the second column should be "4 (32 bit)" AFAIK, but definitely not 8 bytes / 32 bit.
- agounaris 10y agoNice info but... "It is crucial for programmers to understand how long a certain operation takes in and out of a computer." Google interview question "how much time it takes to Read 4K randomly from SSD".... You are hired now go fix this css colour of www.whatever.com/about. :D I would prefer its a "good to know" but not really that crucial unless you create code which operate on such a low level.
- Sean1708 10y agoI honestly think that we don't champion domain specific knowledge enough in software development, there's so many different aspects of software development nowadays and you just can't be expected to be an expert in all of it.
- falsedan 10y agoThis stuff is more "good to show you know it (in the screening call)". It reads like a collection of shibboleths which signal "yes hello I am computer person".
- Tloewald 10y agoSSDs weren't a thing gen years ago and may not be a thing in ten years. This is not eternal fundamental knowledge. The important thing is that registers are way faster than on chip cache which is way faster than ... insert levels of indirection ... which is way faster than ... insert levels of remoteness. Even registers vs on chip cache may not be around that long (probably will for a good long time though). What's actually surprising is that it might be faster to pull data from elsewhere in a data center than your own SSD. I recall John Carmack saying he could ping a server in Europe faster than he could get a pixel onto a display (triple buffered updates at 120fps iirc)
- 110011 10y agoThe latency numbers shown in the post are directly taken from a well known source (see for example https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832). Why the lack of acknowledgement though? As a related rant, let me point out that the standard for quoting seems really poor in these kind blog posts that appear on HN. I wish the authors would take more responsibility and cite sources where credit is due.
- marcosdumay 10y agoCan we stop pretending that the default C integer types have any kind of definitive size? That is wrong, and it's just asking for more portability bugs down the line. The correct sizes: - char >= 1 byte - int, short >= 2 bytes - long >= 4 bytes - long log >= 8 bytes You can not rely on any further information about them.
- peapicker 10y agoYou can't even rely on that... long --> 4 bytes in 32 bit builds everywhere I've used. long --> 4 bytes in 64 bit builds on windows and OS/400, 8 bytes in almost all 64 bit builds on UNIXs that I've used (HPUX,Solaris,Linux,AIX).
- AnimalMuppet 10y agoIn marcosdumay's comment, those were greater-than-or-equals, not arrows.
- lanna 10y agoIt says it there on the page: "It depends on OS by OS but, most commonly…"
- marcosdumay 10y agoIt also varies from one compiler to another, and on a few different versions on the same compiler. It also varies on the same OS, same compiler but different target architecture. And that's now. Who knows if it won't vary due to compiler optimizations in the future? It is wrong to rely on anything more than what it says on the standard.
- jwilk 10y agochar is 1 byte exactly.
- John23832 10y agoA char is 1 byte on most systems, but the actual standard defines it as having CHAR_BITS number of bits. Modern C defines CHAR_BITS as CHAR_BITS >= 8. Some older machines have 7 bits. Theres nothing stopping machines from changing what CHAR_BITS is. <Limits.h>
- weissi 10y agofor int m[2][3] = { {1, 2, 3}, {4, 5,6}}; int *n[2]; n[0] = &m[0][0]; //equivalent to n[0] = m[0] n[1] = &m[1][0]; //equivalent to n[1] = m[1] it lists that What is n[1][1]? //2 What is m[1][1]? //same as n[1][1] but it's actually 5. (n[0][1] would be 2)
- clarkmoody 10y agoTo the site author: Let me just say that I loved how quickly this site loaded. Thank you for taking the effort to build a fast site.