4 ms·

Little endian is natural memory ordering and was specified in Von Neumman's EDVAC design doc during world war ii, so the question isn't so much, "why little end

by jart 7y ago

Little endian is natural memory ordering and was specified in Von Neumman's EDVAC design doc during world war ii, so the question isn't so much, "why little endian?" but rather, "why not?" Only reason computers were ever designed to use "traditional" ordering is because business mainframes loved BCD and they loved to code GUIs that just blit'd raw fixed memory onto the display driver.

tomxor 7y ago
> Only reason computers were ever designed to use "traditional" ordering is because business mainframes loved BCD and they loved to code GUIs that just blit'd raw fixed memory onto the display driver. Hah, so it's literally because we write numbers with most significant digit on the left, which is the opposite to logical ordering? I presume the only advantage to BE today is compatibility then...
- KMag 7y ago
  If you want your (vector or scalar) integer instructions to be useful for fast strcmp/memcmp implementations, then you'll want to support unsigned big-endian integers. Also, if you want to mix integers and strings in compound b+ tree keys and use memcmp to compare keys, you'll want to store your integers big-endian.
  - tomxor 7y ago
    Ah, but isn't that all part of the same quirk of human language, i.e that we compare strings from left most significant to right least significant?
    - KMag 7y ago
      It's not some quirk. There are two common endiannesses, and the byte sort precedence of one of them matches the byte sort precedence we use for text. Since we represent characters as numbers, and for efficiency we have CPU instructions that treat aggregations of these numbers as larger numbers, we can get double-duty out of these instructions/circuits if the order they use is the same as the lexographic ordering of our text. I'm not saying big-endian is universally better. I'm just saying there are real-world advantages. Note there are more than two endiannesses, where the most common middle-endian variant is big-endian order of 16-bit words, but little-endian order within those 16-bit words. As for linguistic quirks, there's no obvious universal connection between writing order for text, the order digits are written, and the way numbers are pronounced, so I'm not sure what you're getting at. Arabic is written right-to-left, but they still write the most significant digit on the left. However, I've read that Arabic writers line-break numbers (when forced) by placing the most significant digits on the upper line and the least significant digits on the lower line, so it's not a clear-cut case of Arabic writing numbers in little-endian order right-to-left. I'm not sure about Arabic number pronunciation. I do know that German pronunciation is middle-endian: 256 is "two hundred six-and-fifty", despite the digit writing order being big-endian in German. I met a German guy who incorrectly swaps digits if you talk to him in English while he's doing mental math... forcing him to process English somehow also swaps digit orders in his head.
  - jart 7y ago
    I don't believe you. That sounds more like bitreverse and morton interleaving. If you're serious that it's actually big endian and that it has a real use case (outside human social traditions and legacy infrastructure maintainence), then I'd love to see convincing details. As for strings, GCC/Clang are great at vectorizing normal byte-oriented code. It doesn't matter if it generates or you hand code VPCMPEQB vs. VPCMPEQQ either, since they appear to have the exact same latency. Modern compilers have also been moving in the direction of punishing folks who do things like `* (uint32_t * )p`, due to aliasing rules rather than endianness. Rob Pike had an amusing blog post on this subject: https://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html https://commandcenter.blogspot.com/2012/04/byte-order-fallac...
    - KMag 7y ago
      > I don't believe you. That sounds more like bitreverse and morton interleaving. If you're serious that it's actually big endian and that it has a real use case (outside human social traditions and legacy infrastructure maintainence), then I'd love to see convincing details. Back when I worked on Google's indexing system (2006-2010), one of the stages keyed documents by URL (with the host name in DNS order: com.google.www) followed by a big-endian timestamp. This put records for the same domain together, and put successive crawls for the same URL in chronological order. This improved compression ratios in our BigTable tablets, and finding the latest crawled version of <URL> was just a search for the largest key <= <URL><MAX_TIMESTAMP>. > It doesn't matter if it generates or you hand code VPCMPEQB vs. VPCMPEQQ either, since they appear to have the exact same latency. But with VPCMPEQB, you need to have 8 times as many conditional branches as CPCMPEQQ (in the naive case) in order to turn your vectorized comparison into a memcmp result. Note that VCMPEQ* don't modify any flags, so you can't just JE/JNE after your VCMPEQ*. Now, via some vector permutes, shifts, and bitwise-ors, you can cut down on the number of conditional branches. However, it's still more processing than if you can load / compare your vector registers in lexographical order.
      - jart 7y ago
        But Google doesn't use big endian CPUs in prod, so you've proven the point yourself. I agree that lexicographically arranging things can have an awesome impact on performance though. Still think that has zero to do with endianness. > But with VPCMPEQB, you need to have 8 times as many conditional branches as CPCMPEQQ in order to turn your vectorized comparison into a memcmp result Not at all. It doesn't require any branches, other than the loop itself. Here's the trick everyone uses, for the simple case of finding one character, e.g. NUL: 0: add $vectorlen,i pmovdqa mem,vector pcmpeqb query,vector pmovmskb vector,bitmask bsf bitmask,offset jz 0b add offset,i ret BSF gives you the byte offset of the match, and bam you're done.
- gumby 7y ago
  “We” being people with left-to-right languages. All rtl languages I know of write numbers the same as ltr languages, i.e. in the rtl case little endian. As you have to read an entire positional number to be able to get even its magnitude; the only “advantage” I can see of LE over BE in natural languages is that at least rtl can get odd/even immediately. Then again in ltr you can get sign immediately. In real life human use neither “advantage” is compelling.
KMag 7y ago
As I mentioned elsewhere, the fact that big-endian positive integers (and IEEE-754 normalized floats/doubles) sort the same lexographically and numerically is useful. The same goes for UTF-8-like big-endian encodings for variable length integers and ISO 8601-formatted dates / times. It's handy to be able to use memcmp() on compound b+ tree keys. The advantage works both ways: it's also nice if your normal integer vector instructions can be used to accelerate memcmp, without needing an extra opcode or instruction flag to specifically support parallel lexographical comparison. Note that if the vector units only support signed integers, then you only need an exclusive-or to flip all of the sign bits in order to get lexographical sorting, and that vector exclusive-or has important real-word use cases for hash functions and so-called add-shift-xor encryption algorithms like ChaCha20. Alternatively, if you're going to include a dedicated lexographical comparison instruction for strcmp/memcmp (like x86 REP CMPS), a fast implementation will need less dedicated circuitry if your processor natively supports big-endian operations for other instructions. Big-endian use in mainframes likely evolved from big-endian BCD numeric fields on punch card sorting/tabulating machines, where big-endianness was an advantage in that the normal lexographic sorting would put constant-width numeric fields in numerical order.
- jart 7y ago
  SWAR techniques are orthogonal to endianness. Read Hacker's Delight; it mentions big endian only once, to explain how to convert away from it. Describing variable-length encoding as big-endian-like is quite a creative stretch. Xor does not flip two's complement sign correctly, except in a few special cases like YCbCr. Please read the EDVAC design doc, since Von Neumman invented two's complement too. His ideas are the reason why programmers have never needed to care much about whether it's signed or unsigned, since the machine arithmetic will behave exactly the same way (with few exceptions).
  - KMag 7y ago
    > Describing variable-length encoding as big-endian-like is quite a creative stretch. LEB128 is a little-endian variable-length encoding. That's what the LE stands for. UTF-8 is a big-endian variable-length encoding. The most significant bits are packed in the earlier bytes, so that lexographic ordering comes out correctly. I'm really alluding to something like LEB128-encoding uint64_ts, except big-endian and putting all of the continuation flags at the beginning of the encoding, so a single switch on the first byte gives you the encoded length and it also sorts correctly lexographically. > Xor does not flip two's complement sign correctly Re-read what I wrote. I wasn't talking about flipping the sign bit in order to negate the numeric value. I was talking about flipping the sign bit to get correct lexographic text ordering on a machine that can only do signed comparisons. > since the machine arithmetic will behave exactly the same way (with few exceptions). I was talking about _exactly_ one of these exceptions... comparing two values. For simplicity, let's pretend we have a 16-bit BE CPU that can only perform signed comparisons, and we want to lexographically compare two 4-byte arrays: [ 41 4F 4F 4F ] vs. [ C1 81 4F 4F ] we perform the first load to compare 0x414F (16719) vs. 0xC181 (-15999) in order to get the correct lexographical ordering in all cases, we need to invert the sense of the sign bit. Flipping the sign bit in these two cases gives 0xC14F (-16049) vs 0x8181 (33153). In all cases, flipping the sign bit allows one to perform unsigned comparison on a CPU that can only perform signed comparisons. For an W-bit word, you end up subtracting (W-1)^2 from all values with the most significant bit unset and adding (W-1)^2 to all values with the most significant bit set. I understand this doesn't negate the values. That's not the point. The point is to perform unsigned comparison on a CPU that doesn't natively support it.

by jart 7y ago

tomxor 7y ago

> Only reason computers were ever designed to use "traditional" ordering is because business mainframes loved BCD and they loved to code GUIs that just blit'd raw fixed memory onto the display driver. Hah, so it's literally because we write numbers with most significant digit on the left, which is the opposite to logical ordering? I presume the only advantage to BE today is compatibility then...

KMag 7y ago
If you want your (vector or scalar) integer instructions to be useful for fast strcmp/memcmp implementations, then you'll want to support unsigned big-endian integers. Also, if you want to mix integers and strings in compound b+ tree keys and use memcmp to compare keys, you'll want to store your integers big-endian.
- tomxor 7y ago
  Ah, but isn't that all part of the same quirk of human language, i.e that we compare strings from left most significant to right least significant?
  - KMag 7y ago
    It's not some quirk. There are two common endiannesses, and the byte sort precedence of one of them matches the byte sort precedence we use for text. Since we represent characters as numbers, and for efficiency we have CPU instructions that treat aggregations of these numbers as larger numbers, we can get double-duty out of these instructions/circuits if the order they use is the same as the lexographic ordering of our text. I'm not saying big-endian is universally better. I'm just saying there are real-world advantages. Note there are more than two endiannesses, where the most common middle-endian variant is big-endian order of 16-bit words, but little-endian order within those 16-bit words. As for linguistic quirks, there's no obvious universal connection between writing order for text, the order digits are written, and the way numbers are pronounced, so I'm not sure what you're getting at. Arabic is written right-to-left, but they still write the most significant digit on the left. However, I've read that Arabic writers line-break numbers (when forced) by placing the most significant digits on the upper line and the least significant digits on the lower line, so it's not a clear-cut case of Arabic writing numbers in little-endian order right-to-left. I'm not sure about Arabic number pronunciation. I do know that German pronunciation is middle-endian: 256 is "two hundred six-and-fifty", despite the digit writing order being big-endian in German. I met a German guy who incorrectly swaps digits if you talk to him in English while he's doing mental math... forcing him to process English somehow also swaps digit orders in his head.
- jart 7y ago
  I don't believe you. That sounds more like bitreverse and morton interleaving. If you're serious that it's actually big endian and that it has a real use case (outside human social traditions and legacy infrastructure maintainence), then I'd love to see convincing details. As for strings, GCC/Clang are great at vectorizing normal byte-oriented code. It doesn't matter if it generates or you hand code VPCMPEQB vs. VPCMPEQQ either, since they appear to have the exact same latency. Modern compilers have also been moving in the direction of punishing folks who do things like `* (uint32_t * )p`, due to aliasing rules rather than endianness. Rob Pike had an amusing blog post on this subject: https://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html https://commandcenter.blogspot.com/2012/04/byte-order-fallac...
  - KMag 7y ago
    > I don't believe you. That sounds more like bitreverse and morton interleaving. If you're serious that it's actually big endian and that it has a real use case (outside human social traditions and legacy infrastructure maintainence), then I'd love to see convincing details. Back when I worked on Google's indexing system (2006-2010), one of the stages keyed documents by URL (with the host name in DNS order: com.google.www) followed by a big-endian timestamp. This put records for the same domain together, and put successive crawls for the same URL in chronological order. This improved compression ratios in our BigTable tablets, and finding the latest crawled version of <URL> was just a search for the largest key <= <URL><MAX_TIMESTAMP>. > It doesn't matter if it generates or you hand code VPCMPEQB vs. VPCMPEQQ either, since they appear to have the exact same latency. But with VPCMPEQB, you need to have 8 times as many conditional branches as CPCMPEQQ (in the naive case) in order to turn your vectorized comparison into a memcmp result. Note that VCMPEQ* don't modify any flags, so you can't just JE/JNE after your VCMPEQ*. Now, via some vector permutes, shifts, and bitwise-ors, you can cut down on the number of conditional branches. However, it's still more processing than if you can load / compare your vector registers in lexographical order.
    - jart 7y ago
      But Google doesn't use big endian CPUs in prod, so you've proven the point yourself. I agree that lexicographically arranging things can have an awesome impact on performance though. Still think that has zero to do with endianness. > But with VPCMPEQB, you need to have 8 times as many conditional branches as CPCMPEQQ in order to turn your vectorized comparison into a memcmp result Not at all. It doesn't require any branches, other than the loop itself. Here's the trick everyone uses, for the simple case of finding one character, e.g. NUL: 0: add $vectorlen,i pmovdqa mem,vector pcmpeqb query,vector pmovmskb vector,bitmask bsf bitmask,offset jz 0b add offset,i ret BSF gives you the byte offset of the match, and bam you're done.
gumby 7y ago
“We” being people with left-to-right languages. All rtl languages I know of write numbers the same as ltr languages, i.e. in the rtl case little endian. As you have to read an entire positional number to be able to get even its magnitude; the only “advantage” I can see of LE over BE in natural languages is that at least rtl can get odd/even immediately. Then again in ltr you can get sign immediately. In real life human use neither “advantage” is compelling.

KMag 7y ago

As I mentioned elsewhere, the fact that big-endian positive integers (and IEEE-754 normalized floats/doubles) sort the same lexographically and numerically is useful. The same goes for UTF-8-like big-endian encodings for variable length integers and ISO 8601-formatted dates / times. It's handy to be able to use memcmp() on compound b+ tree keys. The advantage works both ways: it's also nice if your normal integer vector instructions can be used to accelerate memcmp, without needing an extra opcode or instruction flag to specifically support parallel lexographical comparison. Note that if the vector units only support signed integers, then you only need an exclusive-or to flip all of the sign bits in order to get lexographical sorting, and that vector exclusive-or has important real-word use cases for hash functions and so-called add-shift-xor encryption algorithms like ChaCha20. Alternatively, if you're going to include a dedicated lexographical comparison instruction for strcmp/memcmp (like x86 REP CMPS), a fast implementation will need less dedicated circuitry if your processor natively supports big-endian operations for other instructions. Big-endian use in mainframes likely evolved from big-endian BCD numeric fields on punch card sorting/tabulating machines, where big-endianness was an advantage in that the normal lexographic sorting would put constant-width numeric fields in numerical order.

jart 7y ago
SWAR techniques are orthogonal to endianness. Read Hacker's Delight; it mentions big endian only once, to explain how to convert away from it. Describing variable-length encoding as big-endian-like is quite a creative stretch. Xor does not flip two's complement sign correctly, except in a few special cases like YCbCr. Please read the EDVAC design doc, since Von Neumman invented two's complement too. His ideas are the reason why programmers have never needed to care much about whether it's signed or unsigned, since the machine arithmetic will behave exactly the same way (with few exceptions).
- KMag 7y ago
  > Describing variable-length encoding as big-endian-like is quite a creative stretch. LEB128 is a little-endian variable-length encoding. That's what the LE stands for. UTF-8 is a big-endian variable-length encoding. The most significant bits are packed in the earlier bytes, so that lexographic ordering comes out correctly. I'm really alluding to something like LEB128-encoding uint64_ts, except big-endian and putting all of the continuation flags at the beginning of the encoding, so a single switch on the first byte gives you the encoded length and it also sorts correctly lexographically. > Xor does not flip two's complement sign correctly Re-read what I wrote. I wasn't talking about flipping the sign bit in order to negate the numeric value. I was talking about flipping the sign bit to get correct lexographic text ordering on a machine that can only do signed comparisons. > since the machine arithmetic will behave exactly the same way (with few exceptions). I was talking about _exactly_ one of these exceptions... comparing two values. For simplicity, let's pretend we have a 16-bit BE CPU that can only perform signed comparisons, and we want to lexographically compare two 4-byte arrays: [ 41 4F 4F 4F ] vs. [ C1 81 4F 4F ] we perform the first load to compare 0x414F (16719) vs. 0xC181 (-15999) in order to get the correct lexographical ordering in all cases, we need to invert the sense of the sign bit. Flipping the sign bit in these two cases gives 0xC14F (-16049) vs 0x8181 (33153). In all cases, flipping the sign bit allows one to perform unsigned comparison on a CPU that can only perform signed comparisons. For an W-bit word, you end up subtracting (W-1)^2 from all values with the most significant bit unset and adding (W-1)^2 to all values with the most significant bit set. I understand this doesn't negate the values. That's not the point. The point is to perform unsigned comparison on a CPU that doesn't natively support it.