33 ms·

For example, if you had a file that comprised the following struct: struct someblob { uint64_t timestamp; uint64_t checksum; uint32

For example, if you had a file that comprised the following struct: struct someblob { uint64_t timestamp; uint64_t checksum; uint32_t item_count; struct something items[0]; }; Even if you didn't know that a collection of files were structured this way, you could still read, say, the first 128 bits as an unsigned integer and compare them, and they'd just happen to be naturally ordered because the timestamp field grows from right to left, and would have precedence over the "lower 64 bits" of the checksum field. It's a very minor benefit (of dubious real-world utility), but I wanted to be comprehensive :P

tekacs 2y ago
This comes in really really handy in lexicographical ordering. For example, if storing in the keys of a KV store a pattern of: [u32, String, u32, String, …] If you want those arrays to be sorted lexicographically, you’ll want to store those u32 instances in big endian, so that both those and the strings sort from left-to-right.
weinzierl 2y ago
Thanks! That makes sense. Mentally, I would put this in the "conventional" advantage category, because it relies on comparing fixed length chunks of memory and computationally it should not make a difference if `timestamp` is stored LE or BE for sorting.
- kstenerud 2y ago
  Actually, in this case it would. Consider the layout (byte-by-byte): BE: t8 t7 t6 t5 t4 t3 t2 t1 c8 c7 c6 c5 c4 c3 c2 c1 In the big endian case, the byte-by-byte of the struct naturally places the timestamp at the high end of the 128 bit value you blindly read. LE: t1 t2 t3 t4 t5 t6 t7 t8 c1 c2 c3 c4 c5 c6 c7 c8 In the little endian case, it's the CHECKSUM at the high end of the 128 bit value.
  - weinzierl 2y ago
    I think we agree, but it nags me that I still can't follow your line of thought. Do you want to: - Compare just the timestamp, so 1970-01-01 00:00 0x01 1970-01-01 00:00 0x00 1970-01-01 00:00 0x01 1970-01-01 00:01 0x01 1970-01-01 00:01 0x00 1970-01-01 00:01 0x01 could be a valid ordering, with the first three and last three in arbitrary ordering, because the checksum doesn't play a role. - Compare timestamp and checksum, in the sense of ordering all files with the same checksum by timestamp, like this 1970-01-01 00:00 0x00 1970-01-01 00:01 0x00 1970-01-01 00:02 0x00 1970-01-01 00:00 0x01 1970-01-01 00:01 0x01 1970-01-01 00:02 0x01 - Compare timestamp and checksum, in the sense that files with the same timestamp are ordered by checksum, in effect grouping equal checksum files together under their respective date. 1970-01-01 00:00 0x00 1970-01-01 00:00 0x01 1970-01-01 00:00 0x02 1970-01-01 00:01 0x01 1970-01-01 00:01 0x02 1970-01-01 00:01 0x02 1970-01-01 00:01 0x03 In the first case you could just compare the first 64-bit, so I don't think that's it. The second case would be an advantage for little-endian, so it doesn't support your argument. Third case supports the argument for BE, but is an unusual thing to want. In other words: Is the checksum crucial for your line of argumentation, or could you make your point with just a timestamp? If not, why not compare just 64-bit. If yes, I don't follow why BE is better in this case.
    - kstenerud 2y ago
      Basically, (and this is getting really esoteric at this point), if you use big endian byte ordering in your data structures when saving to disk, then you can place items in order of descending "sorting order" importance at the beginning of your file. Anyone wishing to sort such files wouldn't need to know anything about the actual structure of the file, or what is stored where. They could simply choose an arbitrary number of bits to read (say, 512 bits), do a big endian sort based on that, and it will always come out right (even though they're technically reading more than they have to). struct myfile { uint32_t year; uint8_t month; // Assuming packed structs here uint8_t day; uint32_t seconds; uint16_t my_custom_ordering; uint8_t some_flags; uint64_t a_checksum_or_something; char name[100]; ... } Reading the first 64 bytes from this file will give year, then month, then day, then seconds, then my_custom_ordering, then some_flags, then a_checksum_or_something, then the first few bytes of name (assuming we used big endian byte ordering). The extra bytes won't hurt anything because they're lower order when we compare. To do this with little endian ordered data, you would have to: 1) Reverse the ordering of the "sortable" fields to: my_custom_ordering, seconds, day, month, year 2) Know in advance that you have to read exactly 12 bytes (no more, no less) from any file using this structure. If you read any more, you'll get random ordering based on the reverse of what's in the "name", "a_checksum_or_something", and "some_flags" fields (because they comprise the "higher order" bytes when reading little endian). 3) If you were to add another field "my_extra_custom_ordering", you'd have to adjust the number of bytes you read. With big endian ordering, you can still read 64 bytes and not care. You'd only care once your "sortable fields" exceeds 64 bytes - at which point you'd read, say, 100 bytes to be completely arbitrary... It doesn't matter because with BE everything just sorts itself out. The comparator function is also much simpler with BE: Just do a byte-by-byte compare until you find a difference. With LE, you have to start at a specific offset (in the above case, 11) and decrement towards 0.
- foldr 2y ago
  A simpler case is reading only a fraction of a field. For example, suppose that you have a 8 byte key and you read the first four bytes of it. On a big-endian architecture, those are the high bytes and you can sort with them just fine (up to some level of detail). On a little-endian architecture, you'll be sorting by the lower bytes and the results will be meaningless. So the big-endian architecture allows you to sort by the first n bytes of a struct without caring what fields it contains. While there is obviously no guarantee that the results of this will be meaningful in the general case, it is far more likely than for a little-endian architecture.
  - weinzierl 2y ago
    My counter argument to this would be that it is as expensive to compare LE k[4]s with each other as it is BE k[0]s. As long as you deal with fixed length chunks of data accessing it from either end should be equal effort (in first approximation[1]). This is qualitatively different from the odd/even case, because for a number of unknown length you can tell odd/even in O(1) for LE but need O(n) only for BE (you have to find the LSB in n steps). Mathematically there is more information you get from just having the LSBs than just having the MSBs without knowing the whole number and its length. I think this the only reason, why LE is marginally better, everything else boils down to convention. [1] I know that on modern architectures it can be faster to read memory upwards than downwards, because of the pre-fetcher, but this is what I meant with the advantage is because of convention. If we had a symmetric pre-fetcher the point would be moot.
    - foldr 2y ago
      True. There is a significant asymmetry, though, in that you are more likely to be in a situation where you know the starting address of an object and a minimum size than you are to be in a situation where you know the end address of an object and a minimum size. Strictly speaking that's also an arbitrary convention (as I guess the address of a struct could be defined as the address of its last byte), but it's a near-universal one.

tekacs 2y ago

This comes in really really handy in lexicographical ordering. For example, if storing in the keys of a KV store a pattern of: [u32, String, u32, String, …] If you want those arrays to be sorted lexicographically, you’ll want to store those u32 instances in big endian, so that both those and the strings sort from left-to-right.

weinzierl 2y ago

Thanks! That makes sense. Mentally, I would put this in the "conventional" advantage category, because it relies on comparing fixed length chunks of memory and computationally it should not make a difference if `timestamp` is stored LE or BE for sorting.

kstenerud 2y ago
Actually, in this case it would. Consider the layout (byte-by-byte): BE: t8 t7 t6 t5 t4 t3 t2 t1 c8 c7 c6 c5 c4 c3 c2 c1 In the big endian case, the byte-by-byte of the struct naturally places the timestamp at the high end of the 128 bit value you blindly read. LE: t1 t2 t3 t4 t5 t6 t7 t8 c1 c2 c3 c4 c5 c6 c7 c8 In the little endian case, it's the CHECKSUM at the high end of the 128 bit value.
- weinzierl 2y ago
  I think we agree, but it nags me that I still can't follow your line of thought. Do you want to: - Compare just the timestamp, so 1970-01-01 00:00 0x01 1970-01-01 00:00 0x00 1970-01-01 00:00 0x01 1970-01-01 00:01 0x01 1970-01-01 00:01 0x00 1970-01-01 00:01 0x01 could be a valid ordering, with the first three and last three in arbitrary ordering, because the checksum doesn't play a role. - Compare timestamp and checksum, in the sense of ordering all files with the same checksum by timestamp, like this 1970-01-01 00:00 0x00 1970-01-01 00:01 0x00 1970-01-01 00:02 0x00 1970-01-01 00:00 0x01 1970-01-01 00:01 0x01 1970-01-01 00:02 0x01 - Compare timestamp and checksum, in the sense that files with the same timestamp are ordered by checksum, in effect grouping equal checksum files together under their respective date. 1970-01-01 00:00 0x00 1970-01-01 00:00 0x01 1970-01-01 00:00 0x02 1970-01-01 00:01 0x01 1970-01-01 00:01 0x02 1970-01-01 00:01 0x02 1970-01-01 00:01 0x03 In the first case you could just compare the first 64-bit, so I don't think that's it. The second case would be an advantage for little-endian, so it doesn't support your argument. Third case supports the argument for BE, but is an unusual thing to want. In other words: Is the checksum crucial for your line of argumentation, or could you make your point with just a timestamp? If not, why not compare just 64-bit. If yes, I don't follow why BE is better in this case.
  - kstenerud 2y ago
    Basically, (and this is getting really esoteric at this point), if you use big endian byte ordering in your data structures when saving to disk, then you can place items in order of descending "sorting order" importance at the beginning of your file. Anyone wishing to sort such files wouldn't need to know anything about the actual structure of the file, or what is stored where. They could simply choose an arbitrary number of bits to read (say, 512 bits), do a big endian sort based on that, and it will always come out right (even though they're technically reading more than they have to). struct myfile { uint32_t year; uint8_t month; // Assuming packed structs here uint8_t day; uint32_t seconds; uint16_t my_custom_ordering; uint8_t some_flags; uint64_t a_checksum_or_something; char name[100]; ... } Reading the first 64 bytes from this file will give year, then month, then day, then seconds, then my_custom_ordering, then some_flags, then a_checksum_or_something, then the first few bytes of name (assuming we used big endian byte ordering). The extra bytes won't hurt anything because they're lower order when we compare. To do this with little endian ordered data, you would have to: 1) Reverse the ordering of the "sortable" fields to: my_custom_ordering, seconds, day, month, year 2) Know in advance that you have to read exactly 12 bytes (no more, no less) from any file using this structure. If you read any more, you'll get random ordering based on the reverse of what's in the "name", "a_checksum_or_something", and "some_flags" fields (because they comprise the "higher order" bytes when reading little endian). 3) If you were to add another field "my_extra_custom_ordering", you'd have to adjust the number of bytes you read. With big endian ordering, you can still read 64 bytes and not care. You'd only care once your "sortable fields" exceeds 64 bytes - at which point you'd read, say, 100 bytes to be completely arbitrary... It doesn't matter because with BE everything just sorts itself out. The comparator function is also much simpler with BE: Just do a byte-by-byte compare until you find a difference. With LE, you have to start at a specific offset (in the above case, 11) and decrement towards 0.
foldr 2y ago
A simpler case is reading only a fraction of a field. For example, suppose that you have a 8 byte key and you read the first four bytes of it. On a big-endian architecture, those are the high bytes and you can sort with them just fine (up to some level of detail). On a little-endian architecture, you'll be sorting by the lower bytes and the results will be meaningless. So the big-endian architecture allows you to sort by the first n bytes of a struct without caring what fields it contains. While there is obviously no guarantee that the results of this will be meaningful in the general case, it is far more likely than for a little-endian architecture.
- weinzierl 2y ago
  My counter argument to this would be that it is as expensive to compare LE k[4]s with each other as it is BE k[0]s. As long as you deal with fixed length chunks of data accessing it from either end should be equal effort (in first approximation[1]). This is qualitatively different from the odd/even case, because for a number of unknown length you can tell odd/even in O(1) for LE but need O(n) only for BE (you have to find the LSB in n steps). Mathematically there is more information you get from just having the LSBs than just having the MSBs without knowing the whole number and its length. I think this the only reason, why LE is marginally better, everything else boils down to convention. [1] I know that on modern architectures it can be faster to read memory upwards than downwards, because of the pre-fetcher, but this is what I meant with the advantage is because of convention. If we had a symmetric pre-fetcher the point would be moot.
  - foldr 2y ago
    True. There is a significant asymmetry, though, in that you are more likely to be in a situation where you know the starting address of an object and a minimum size than you are to be in a situation where you know the end address of an object and a minimum size. Strictly speaking that's also an arbitrary convention (as I guess the address of a struct could be defined as the address of its last byte), but it's a near-universal one.