6 ms·

One thing directly connected to this history is why the x86 is little-endian. As the article explains, the 8008 was designed for the Datapoint 2200 terminal. Th

by kens 7y ago

One thing directly connected to this history is why the x86 is little-endian. As the article explains, the 8008 was designed for the Datapoint 2200 terminal. The 8008 was intended as a compatible replacement for the existing Datapoint processor, which was built from simple TTL chips. To reduce the chip count, the Datapoint 2200 used a serial processor, which processed one bit at a time, so you had a 1-bit ALU among other things. One consequence is that you have to start with the low-order bit when doing addition, so you can handle carries. And for 16-bit values, you also have to start with the low-order byte. This forces you into a little-endian architecture. Thus, to be compatible with the Datapoint 2200, the 8008 was also made little-endian. Unfortunately, Intel was very slow creating the 8008, so Datapoint had moved on to a parallel 74181-based architecture and didn't want the 8008. Intel decided to sell the 8008 as a stand-alone product, essentially creating the microprocessor industry. As the article explains, the x86 grew out of the 8008, so x86 also inherited the little-endian architecture

kps 7y ago
Simarly, x86_64 condition codes have a parity flag because the terminal needed it.
Vogtinator 7y ago
I don't think that really forced any particular endianness. Endianness is only really a thing if there's addressable memory, which is not the case for a bit stream. Whether a system is big/little/mixed-endian was only a question of how the address lines are set for multi-byte accesses.
- tomxor 7y ago
  I thought that too at first, but then I found this stack-overflow answer fairly convincingly confirming the OPs claim with quotes from it's designers: https://stackoverflow.com/a/36263273 https://stackoverflow.com/a/36263273 although it's still not explicitly clear why. > Shustek: So, for example, storing numbers least significant byte first, came from the fact that this was _serial_ and you needed to process the low bits first. > Poor: You had to do it that way. You had no choice. I'm wondering if it was the bit order that mattered for compatibility with the 1-bit serial processor of the Datapoint 2200, and if that determined byte ordering of it's 16bit successor?... I don't know much about 1-bit computing, but if you think about it - to be useful, it must be capable of doing operations on arbitrary length words (within some reasonable limitation), i.e not limited to 8 bits like the 8008. So maybe this put it in a funny position: while byte endianess makes no sense and bit endianness seem to make no difference for the 8008 since it was 8bit; it did make a difference to the datapoint which was serial 1-bit and could operate through the 8bit word boundaries. To be clear what i mean, imagine how a 1-bit ALU would process 16 bits, it would want them in order like this (the bits are in logical order, not numerical order): (8bit) Little Endian: byte 0000000011111111 bit 0123456789abcdef But not like this: (8bit) Big Endian: byte 0000000011111111 bit 76543210fedcba98 I don't know if this is correct, and i'm assuming here that bit endianness must determine byte endianness in the 16bit 8086. Clarification/correction is most welcome.
  - Gibbon1 7y ago
    Assume you are adding two words one bit at a time with one bit of storage for the carry. You can do that with LE but not BE.
    - tomxor 7y ago
      Can you please give a bit more detail? what I don't quite understand is why it would be a problem to do so in reverse bit order? I'm assuming you are saying it's not about word boundaries? that was just my guess, but is it correct that bit order does matter?
      - JoeAltmaier 7y ago
        The carry between bytes can be applied as-you-go with LE but has to be done after with BE. Which would double the execution time (adding zero/1 to each byte of the result).
      - Gibbon1 7y ago
        When you add two binary numbers the simplest method for handling the carry is a ripple carry. The carry bit ripples up from lsb to msb. If you're trying to build a simple 1 bit ALU you only need to save the carry bit as long as you add the bits from least significant to most. if you do it the reverse you have an intermediate result that needs to be saved. One bit ALU adds like a0 + b0 => r0 + carry0 a1 + b1 + carry0 => r1 + carry1 a2 + b2 + carry1 => r1 + carry2 ... an + bn + carry(n-1) => r1 + carryn As you can see you only need to keep the carry bit. The result bit gets written back to memory immediately. What's going on is a 1 bit processor represents the most extreme trade off between gate count and speed for a given functionality. AKA low gate count but requires many clock cycles per operation.
        tomxor 7y ago
        > as long as you add the bits from least significant to most Thanks, although I already understood what you explained, this bit made me realize more clearly the detail I was tripping up on. I was never imagining the 1-bit adder to start anywhere _but_ the LSB, what I couldn't figure out was why it couldn't simply iterate the bits in reverse logical order for big endian... I'm guessing there is a good reason why serial processors can't read a sequence of bits in reverse logical order, and it probably applies to modern CPUs too? either that or it's a design choice that cannot be dynamic. I should probably pick a book up at this point, thanks for answering my questions.
ajross 7y ago
Pretty much all simple multi-word ALU algorithms need to start with the low word first. That particular terminal wasn't remotely unique (though for all I know, it was indeed the specific product that drove the Intel design decision), nor was x86 the first LE architecture. The PDP/11 made the same decision for the same reason several years earlier (and the VAX followed for pseudocompatibility), etc... Really, it wasn't until the mid-80's and the RISC revolution, where all of a sudden people found themselves designing systems that would be 32 bits wide from the very first silicon that the community "decided" that the only true byte order should be BE. And of course, the reason they made that decision was simply that the order of bytes in memory happened to match the way readers of the latin alphabet write arabic numbers on paper. Had the arabs invented computing, there would never even have been a debate.
- userbinator 7y ago
  I've always had it memorised that LE is the "logical" order and BE the "backwards" order, specifically for this reason: with LE, the bit at offset n has value 2^n, and the byte at offset n has value 256^n. With BE it depends on how wide the total value is, which introduces an awkward length-dependent term. Practically all multi-precision arithemtic libraries store the segments of a bignum in LE order too, despite the fact that the individual segments may be BE on a BE machine. That is even more confusing.
- KMag 7y ago
  On the other hand, unsigned big-endian numbers sort lexographically and numerically the same way. So, for instance, if you're using a b+ tree to store time series of key-value pairs, you can use tuples of <key, big_endian_timestamp> as your b+ tree keys and use memcmp() on the raw bytes of your keys. For variable-length integers, using a UTF-8-like big-endian encoding allows you to keep the relationship between lexographic and numeric sorting. This is also a huge advantage of ISO 8601 over other date formats.
- greenyoda 7y ago
  > Really, it wasn't until the mid-80's and the RISC revolution, where all of a sudden people found themselves designing systems that would be 32 bits wide from the very first silicon that the community "decided" that the only true byte order should be BE. IBM 360-series mainframes were 32-bit and big-endian in the 1960s. (Their earlier computers may have been big-endian too, I'm not sure.)
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.

by kens 7y ago

kps 7y ago

Simarly, x86_64 condition codes have a parity flag because the terminal needed it.

Vogtinator 7y ago

I don't think that really forced any particular endianness. Endianness is only really a thing if there's addressable memory, which is not the case for a bit stream. Whether a system is big/little/mixed-endian was only a question of how the address lines are set for multi-byte accesses.

tomxor 7y ago
I thought that too at first, but then I found this stack-overflow answer fairly convincingly confirming the OPs claim with quotes from it's designers: https://stackoverflow.com/a/36263273 https://stackoverflow.com/a/36263273 although it's still not explicitly clear why. > Shustek: So, for example, storing numbers least significant byte first, came from the fact that this was _serial_ and you needed to process the low bits first. > Poor: You had to do it that way. You had no choice. I'm wondering if it was the bit order that mattered for compatibility with the 1-bit serial processor of the Datapoint 2200, and if that determined byte ordering of it's 16bit successor?... I don't know much about 1-bit computing, but if you think about it - to be useful, it must be capable of doing operations on arbitrary length words (within some reasonable limitation), i.e not limited to 8 bits like the 8008. So maybe this put it in a funny position: while byte endianess makes no sense and bit endianness seem to make no difference for the 8008 since it was 8bit; it did make a difference to the datapoint which was serial 1-bit and could operate through the 8bit word boundaries. To be clear what i mean, imagine how a 1-bit ALU would process 16 bits, it would want them in order like this (the bits are in logical order, not numerical order): (8bit) Little Endian: byte 0000000011111111 bit 0123456789abcdef But not like this: (8bit) Big Endian: byte 0000000011111111 bit 76543210fedcba98 I don't know if this is correct, and i'm assuming here that bit endianness must determine byte endianness in the 16bit 8086. Clarification/correction is most welcome.
- Gibbon1 7y ago
  Assume you are adding two words one bit at a time with one bit of storage for the carry. You can do that with LE but not BE.
  - tomxor 7y ago
    Can you please give a bit more detail? what I don't quite understand is why it would be a problem to do so in reverse bit order? I'm assuming you are saying it's not about word boundaries? that was just my guess, but is it correct that bit order does matter?
    - JoeAltmaier 7y ago
      The carry between bytes can be applied as-you-go with LE but has to be done after with BE. Which would double the execution time (adding zero/1 to each byte of the result).
    - Gibbon1 7y ago
      When you add two binary numbers the simplest method for handling the carry is a ripple carry. The carry bit ripples up from lsb to msb. If you're trying to build a simple 1 bit ALU you only need to save the carry bit as long as you add the bits from least significant to most. if you do it the reverse you have an intermediate result that needs to be saved. One bit ALU adds like a0 + b0 => r0 + carry0 a1 + b1 + carry0 => r1 + carry1 a2 + b2 + carry1 => r1 + carry2 ... an + bn + carry(n-1) => r1 + carryn As you can see you only need to keep the carry bit. The result bit gets written back to memory immediately. What's going on is a 1 bit processor represents the most extreme trade off between gate count and speed for a given functionality. AKA low gate count but requires many clock cycles per operation.
      - tomxor 7y ago
        > as long as you add the bits from least significant to most Thanks, although I already understood what you explained, this bit made me realize more clearly the detail I was tripping up on. I was never imagining the 1-bit adder to start anywhere _but_ the LSB, what I couldn't figure out was why it couldn't simply iterate the bits in reverse logical order for big endian... I'm guessing there is a good reason why serial processors can't read a sequence of bits in reverse logical order, and it probably applies to modern CPUs too? either that or it's a design choice that cannot be dynamic. I should probably pick a book up at this point, thanks for answering my questions.

ajross 7y ago

Pretty much all simple multi-word ALU algorithms need to start with the low word first. That particular terminal wasn't remotely unique (though for all I know, it was indeed the specific product that drove the Intel design decision), nor was x86 the first LE architecture. The PDP/11 made the same decision for the same reason several years earlier (and the VAX followed for pseudocompatibility), etc... Really, it wasn't until the mid-80's and the RISC revolution, where all of a sudden people found themselves designing systems that would be 32 bits wide from the very first silicon that the community "decided" that the only true byte order should be BE. And of course, the reason they made that decision was simply that the order of bytes in memory happened to match the way readers of the latin alphabet write arabic numbers on paper. Had the arabs invented computing, there would never even have been a debate.

userbinator 7y ago
I've always had it memorised that LE is the "logical" order and BE the "backwards" order, specifically for this reason: with LE, the bit at offset n has value 2^n, and the byte at offset n has value 256^n. With BE it depends on how wide the total value is, which introduces an awkward length-dependent term. Practically all multi-precision arithemtic libraries store the segments of a bignum in LE order too, despite the fact that the individual segments may be BE on a BE machine. That is even more confusing.
KMag 7y ago
On the other hand, unsigned big-endian numbers sort lexographically and numerically the same way. So, for instance, if you're using a b+ tree to store time series of key-value pairs, you can use tuples of <key, big_endian_timestamp> as your b+ tree keys and use memcmp() on the raw bytes of your keys. For variable-length integers, using a UTF-8-like big-endian encoding allows you to keep the relationship between lexographic and numeric sorting. This is also a huge advantage of ISO 8601 over other date formats.
greenyoda 7y ago
> Really, it wasn't until the mid-80's and the RISC revolution, where all of a sudden people found themselves designing systems that would be 32 bits wide from the very first silicon that the community "decided" that the only true byte order should be BE. IBM 360-series mainframes were 32-bit and big-endian in the 1960s. (Their earlier computers may have been big-endian too, I'm not sure.)

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.