Computer Scientists’ Trivia | Hacker News Reader

Computer Scientists’ Trivia

keon.io

184 pointssigna1172 comments

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

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

Very true, didn't spot that one. Then the C code is probably a typo, but still incorrect. :P

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

> The "replacing multiplication by additions", the replacing multiplication with a shift and the hoisting I mentioned above are all redundant optimisations for a programmer

There's also the fact that the code could get marginally more annoying to maintain, which is honestly more important nowadays even if you were actually saving a few cycles and the compiler wasn't doing the work for you.

The latency numbers shown in the post are directly taken from a well known source (see for example 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.

Hey, thanks for pointing out. I added the reference.

Awesome!

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

It says it there on the page: "It depends on OS by OS but, most commonly…"

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

char is 1 byte exactly.

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

People are talking past each other. In the C standard ‘byte’ means minimum addressable unit — the unit of sizeof — which need not be exactly 8 bits (but in ANSI C must be at least 8 bits). In C, 'char' is one byte, always and exactly. It's also possible for 'long' to be one byte, provided CHAR_BIT≥32.

> In the C standard ‘byte’ means minimum addressable unit — the unit of sizeof

Do you have a reference? I've always seen a byte defined as 8 bits. No matter what. (Unless you're talking to a hard drive manufacturer, that's a different bucket of worms though.)

Orginally? See §7.4 of Planning a Computer System: Project Stretch, edited by Werner Buchholz who coined the term. http://archive.computerhistory.org/resources/text/IBM/Stretc...

For C, see C11 §3.6: “byte — addressable unit of data storage large enough to hold any member of the basic character set of the execution environment” http://www.iso-9899.info/n1570.html#3.6

Makes sense now. Thanks

(From the C99 standard:)

§ 6.5.3.4 The sizeof operator

[…]

Semantics

2 The sizeof operator yields the size (in bytes) of its operand,

[…]

3 When applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.

The draft ISO/IEC 9899:201x PDF of "Programming Languages — C" says:

"3.5 bit

unit of data storage in the execution environment large enough to hold an object that may have one of two values

NOTE It need not be possible to express the address of each individual bit of an object.

3.6 byte

addressable unit of data storage large enough to hold any member of the basic character set of the execution environment

NOTE 1 It is possible to express the address of each individual byte of an object uniquely.

NOTE 2 A byte is composed of a contiguous sequence of bits, the number of which is implementation-defined. The least significant bit is called the low-order bit; the most significant bit is called the high-order bit."

I can't find any indication that a byte is the minimum addressable unit. I guess that is because of 4-bit CPUs and/or CPUs that can address individual bits.

It also uses "byte" very sparingly, most of the time in the context of multibyte (not hyphenated) to single-byte (hyphenated) conversions, but also in section 5.2.1:

"The representation of each member of the source and execution basic character sets shall fit in a byte."

And there also is a guarantee that a unsigned char is as large as a byte in a footnote to section 6.2.6.1:

"A byte contains CHAR_BIT bits, and the values of type unsigned char range from 0 to 2^CHAR_BIT − 1"

I doubt that char and unsinged char can be of different size, but didn't check that.

More accurately, sizeof(char) is always 1. This is simply because sizeof returns the size of the object measured in terms of the equivalent number of chars (rather than 'bytes').

That's not true. sizeof(char) returns 1 because the size of a char in that implementation is 1 byte and C doesn't directly address bits.

Well, according to the Wikipedia article about sizeof,

In the programming languages C and C++, the unary operator sizeof generates the size of a variable or datatype, measured in the number of char size storage units required for the type. As such, the construct sizeof (char) is guaranteed to be 1.

I stand corrected.

You were correct after all. The C99 standard does indeed talk about sizeof in terms of bytes!

I guess this is one of those few times that we can say we were both correct.

Perhaps your notion of what a byte is different, but according to the C99 standard:

- sizeof returns size in bytes;

- sizeof (char) == 1;

- one byte has CHAR_BIT bits;

- CHAR_BIT >= 8.

So per C99, a byte can have more than 8 bits? My mind boggles...

For 36-bit CPUs, the 9-bit byte was a natural choice (as was storing 6 characters of a more limited character set in a 36-bit word)

Ah, yes, 36-bit. I had forgotten about that, despite my mother having worked on such systems.

> - one byte has CHAR_BIT bits;

Can you link a reference to this? Seems backwards/weird.

I was about to jump in and say "no it's not!" but I see several people have pointed out that the C Standard of all things says bytes don't necessarily have 8 bits. Wow!

What I'd like to know is, how common are non-8-bit-byte CPUs these days, for new devices?

I worked with Texas Instruments C54x and C55x DSPs back in the early 2000s (https://en.wikipedia.org/wiki/Texas_Instruments_TMS320#C5000...). They had 16-bit chars and that was incredibly annoying -- very few low-level third-party libraries would even compile properly. Are those still used?

It seems like everything has an ARM chip on the side these days, so maybe (hopefully) there's less need to run application code on bizarre DSPs. Except for those unsung heroes maintaining old set-top boxes and the like.

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

In marcosdumay's comment, those were greater-than-or-equals, not arrows.

> You can not rely on any further information about them.

Not entirely true. One may assume that sizeof(short) <= sizeof(int) <= sizeof(long). In particular, one may cast from short to int and back without loss of information, and likewise from short to long and from int to long.

Anybody who cares about integer sizes in any more detail needs to use things like int32_t.

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

As 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 (?)

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

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

I 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?

Storage devices use the power of 10 units correctly.

My 6TB drive has 6001175126016 bytes.

Windows probably still reports that as 5.5TB, although many Linux GUI tools now correctly say 5.5TiB, or 6TB.

(Being clever should be encouraged!)

That's even worse, because they're intentionally preying on the ignorance in an attempt to make the devices appear to have more space than they actually do.

It depends on the scale. I once got into a discussion that devolved into Tebibytes vs Terabytes for a project. The UI defaulted to TiB but offered a TB option if needed.

If the system has 100 Terabytes of storage - that's a significant difference.

TiB won out btw.

Obligatory Xkcd https://xkcd.com/394/

-1 points? no sense of humour

* Brought to you by, and paid for in full, the Hard Drive Manufacturers Association: "Bringing you quality hard drives that definetly aren't falsely advertised since 1956"

I agree, the "=" (equal) and "~" (approximately) are the wrong around, it should read:

    2^10 ~ Kilo = 10^3
    2^20 ~ Mega = 10^6
    2^30 ~ Giga = 10^9
    2^40 ~ Tera = 10^12

Or, to use the Ki, Mi, etc.

    2^10 = Kibi ~ Kilo = 10^3
    2^20 = Mebi ~ Mega = 10^6
    2^30 = Gibi ~ Giga = 10^9
    2^40 = Tebi ~ Tera = 10^12

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

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

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

SSDs 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)

I 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

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

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

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

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

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

Regardless if it is worth it or not: Every compiler does such basic peephole optimisations.

OT: beautiful choice of colors and fonts for his blog, I was immediately struck by how pleasant it was to read.

I am seriously unable to tell if you are genuinely appreciating the appearance of the blog or sarcastically mocking it.

I think most people would not prefer grey on black fixed width. But it did not bother me that much, personally.

I usually go for green on black in my terminals.

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

MacOsX and Linux terminals support green on black themes out of the box. (Otherwise, I would adopt the white on black option.)

worked well for me here!

Genuine appreciation :)

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

Even that is inaccurate. Long is 4 bytes on 64bit windows, 8 bytes on 64bit UNIXes (all I've used) and 4 bytes on OS/400 with teraspace (an environment with 16 byte pointers)

yeah but certainly 8 bytes are not 32 bit

for

    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)

Beautiful typo about two's complement:

> Simply filp all bits and add 1.

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

Reply on news.ycombinator.com