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.

It's even more ironic given that the author wrote right above that part:

    "Always profile the program’s performance."

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.

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.

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.

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.

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.

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.

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

<Limits.h>

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

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

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

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

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.

- sizeof returns size in bytes;

- sizeof (char) == 1;

- one byte has CHAR_BIT bits;

- CHAR_BIT >= 8.

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

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.

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

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.

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

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

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

TiB won out btw.

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

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

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

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)

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.

I half-remember hearing about memory-prefetchers smart enough to detect this kind of strided access and fill the cache accordingly.

> long 8 (32 bit) 8 (64 bit)

the second column should be "4 (32 bit)" AFAIK, but definitely not 8 bytes / 32 bit.

    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]

  What is n[1][1]? //2
  What is m[1][1]? //same as n[1][1]

> Simply filp all bits and add 1.

Let me just say that I loved how quickly this site loaded. Thank you for taking the effort to build a fast site.