Hacker News Reader

Comment by bregma | Hacker News Reader

And which is the correct byte ordering, pray tell?

Big and little endian are named after the never-ending "holy" war in Gulliver's Travels over how to open eggs. So we were always of the opinion that it doesn't really matter. But I open my eggs on the little end

Big Endian of course :-) However the one which has won is Little Endian. Even IBM admitted this when it switched the default in POWER 7 to little endian. s390x is the only significant architecture that is still big endian.

Little endian has the advantage that you can read the low bits of data without having to adjust the address. So you can for example do long addition in memory order rather than having to go backwards, or (with an appropriate representation such as ULEB128) in one pass without knowing the size.

Maybe I am biased working on mainframes, but I would personally take big endian over little endian. The reason is when reading a hex dump, I can easily read the binary integers from left to right.

That's the only thing that BE has over LE.

But for example bitmaps in BE are a huge source of bugs, as readers and writers need to agree on the size to use for memory operations.

"SIMD in a word" (e.g. doing strlen or strcmp with 32- or 64-bit memory accesses) might have mostly fallen out of fashion these days, but it's also more efficient in LE.

Big endian is easier for humans to read when looking at a memory dump, but little endian has many useful features in binary encoding schemes due to the low byte being first.

I used to like big endian more, but after deep investigation I now prefer little endian for any encoding schemes.

Couldn’t encoding systems be redone with emphasis on the high-order bits? Or is the assumption that the values are clustered in the low bits?

I think the fundamental problems is that if you start a computation using N most significant bits and then incrementally add more bits, e.g. N+M bits total, then your first N bits might change as a result.

E.g. decimal example:

    1.00/1.00 = 1.00
    1.000/1.001 = 0.999000999000...

(adding one more bit changes the first bits of the outcome)

You can put emphasis on high order bits, but that makes decoding more complex. With little endian the decoder builds low to high, which is MUCH easier to deal with, especially on spillover.

For example, with ULEB128 [1], you just read 7 bits at a time, going higher and higher up the value you're reconstituting. If the value grows too big and you need to spill over to the next (such as with big integer implementations), you just fill the last bits of the old value, then put the remainder bits in the next value and continue on.

With a big endian encoding method (i.e. VLQ used in MIDI format), you start from the high bits and work your way down, which is fine until your value spills over. Because you only have the high bits decoded at the time of the spillover, you now have to start shifting bits along each of your already decoded big integer portions until you finally decode the lowest bit. This of course gets progressively slower as the bits and your big integer portions pile up.

Encoding is easier too, since you don't need to check if for example a uint64 integer value can be encoded in 1, 2, 3, 4, 5, 6, 7 or 8 bits. Just encode the low 8 bits, shift the source right by 8, repeat, until the source value is 0. Then backtrack to the as-yet-blank encoded length field in your message and stuff in how many bytes you encoded. You just got the length calculation for free. Use a scheme where you only encode up to 60 bit values, place the length field in the low 4 bits, and Robert's your father's brother!

For data that is right-heavy (i.e. the fully formed data always has real data on the right side and blank filler on the left - such as uint32 value 8 is actually 0x00000008), you want a little endian scheme. For data that is left-heavy, you want a big endian scheme. Since most of the data we deal with is right-heavy, little endian is the way to go.

You can see how this has influenced my encoding design in [2] [3] [4].

[1] https://en.wikipedia.org/wiki/LEB128

[2] https://github.com/kstenerud/concise-encoding/blob/master/cb...

[3] https://github.com/kstenerud/compact-float/blob/master/compa...

[4] https://github.com/kstenerud/compact-time/blob/master/compac...

Middle-endian is the only correct answer. It's a tradeoff between both little-endian and big-endian. The PDP-11 got it right.

Yup, we're all waiting for the rest of the world to catch up to MM/DD/YYYY.

I don't suppose it's being modified, but I wonder how much -11 code is still running, even on real hardware.

Reply on news.ycombinator.com