Once again I’m inventing terms for useful distinctions that programmers need to make and sometimes get confused about because they lack precise language.
The motivation today is some issues that came up while I was trying to refactor some data representations to reduce reposurgeon’s working set. I realized that there are no fewer than three different things we can mean by the “length” of a structure in a language like C, Go, or Rust – and no terms to distinguish these senses.
Before reading these definitions, you might to do a quick read through The Lost Art of Structure Packing.
The first definition is payload length. That is the sum of the lengths of all the data fields in the structure. No padding is included in this length.
The second is stride length. This is the length of the structure with any interior padding and with the trailing padding or dead space required when you have an array of them. This padding is forced by the fact that on most hardware, an instance of a structure normally needs to have the alignment of its widest member for fastest access. If you’re working in C, sizeof gives you back a stride length in bytes.
I derived the term “stride length” for individual structures from a well-established traditional use of “stride” for array programming in PL/1 and FORTRAN that is decades old.
Stride length and payload length coincide if the structure has no interior or trailing padding. This can sometimes happen when you get an arrangement of fields exactly right, or your compiler might have a pragma to force tight packing even though fields may have to be accessed by slower multi-instruction sequences.
“Singleton length” is the term you’re least likely to need. It’s the length of a structure with interior padding but without trailing padding. The reason I’m dubbing it “singleton” length is that it might be relevant in situations where you’re declaring or passing a single instance of a struct not in an array.
Consider the following declarations in C on a 64-bit machine:
struct {int64_t a; int32_t b} x;
char y
That structure has a payload length of 12 bytes. Instances of it in an array would normally have a stride length of 16 bytes, with the last four bytes being padding. But your compiler might generate a 12-byte copy when you ask it to assign the value of x.
This struct has a singleton length of 12, same as its payload length. But these are not necessarily identical, Consider this:
struct {int64_t a; char b[6]; int32_t c} x;
The way this is normally laid out in memory it will have two bytes of interior padding after b, then 4 bytes of trailing padding after c. Its payload length is 8 + 6 + 4 = 18; its stride length is 8 + 8 + 8 = 24; and its singleton length is 8 + 6 + 2 + 4 = 20.
To avoid confusion, you should develop a habit: any time someone speaks or writes about the “length” of a structure, stop and ask: is this payload length, stride length, or singleton length?
Most usually the answer will be stride length. But someday, most likely when you’re working close to the metal on some low-power embedded system, it might be payload or singleton length – and the difference might actually matter.
Even when it doesn’t matter, having a more exact mental model is good for reducing the frequency of times you have to stop and check yourself because a detail is vague. The map is not the territory, but with a better map you’ll get lost less often.
The C standard defines sizeof() to return the stride length, and guarantees that it is possibe to copy objects around with memcpy(). So in most cases, the compiler cannot place another variable inside the trailing padding bytes.
(OTOH the compiler is not required to copy padding bytes when assigning structures.)
>(OTOH the compiler is not required to copy padding bytes when assigning structures.)
Right, that’s a better case to use. As opposed to going into the logic of various cases where the compiler can and cannot prove that the trailing bytes can’t be clobbered. Edited accordingly.
/with the last two bytes being padding/s/two/four/
>/with the last two bytes being padding/s/two/four/
Yep. Thanks for catching that.
Eric, You finally got me!
>Eric, You finally got me!
OK, I’m clueless. Got you what?
BTW, this being Sunday I think we’ll be having our usual order of your supremely succulent barbecue this evening. Expect that call.
If you’re about to update “The Lost Art”, there is a typo in section 12: s/s script/a script/
Minor corrections to 2nd example:
8 + 6 + 4 = 18 so payload length = 18.
8 + 6 + 2 + 4 = 20 so singleton length = 20
>Minor corrections to 2nd example:
What is it with my inability to do arithmetic today? Got the logic right but the sums wrong…
‘singleton’ has another common meaning. Is there a better term available for this subtle (and rare) distinction with sizeof/stride?
>‘singleton’ has another common meaning. Is there a better term available for this subtle (and rare) distinction with sizeof/stride?
I did consider that use in OO as a possible conflict. But I don’t think it’s a problem, since use in the phrase “singleton length” clearly indicates a measure, a very different thing from an object class.
Atom?
Mmm, I don’t think so. “Atom” connotes indivisibility. “Singleton” connotes “you’re only ever going to have one”.
Another consideration is flexible array members (at least in C). Context determines whether the structure “length” should be read to include the array contents or not.
These discussions are important for vectors. I think there is another important discussion when you start expanding in to data arrays: which dimension is the base vector? In an array (x, y, z) which dimension is the elemental vector with contiguous storage? If you address things correctly you are reading from local memory. If not, you may suffer lots of delay while data is fetched from read-ahead cache (if you are lucky) or base storage if you are not..
Or, is this not an issue on systems with many GB of RAM now?
In my distant past I was working on a VAX in FORTRAN and determined (x) was the elemental vector but other programmers just assumed (z) was elemental…
This isn’t directly related, but it’s close enough that it might be on topic. This has been knocking around my head since reading "The lost art of structure packing", "How not to design a wire protocol", and "Declarative is greater than imperative":
Is there a Right Way to specify the format of packed binary data in a declarative form, such that the spec is human-writable and machine-readable? A data structure that defines data structures?
I have a personal project that needs to solve a subset of this problem. The closest thing I could find to the Right Thing was Kaitai Struct, but it’s read-only, and not interpetable at runtime. Other solutions I’ve tried fall down on pathological input — my favorites so far have been a two-bit uint in the middle of a byte, and a 32-bit array of bits used as indices to another array. Also, unions.
I have a suspicion this is just a Hard Problem, but it seems worth asking.
While it is far behind Kaitai Struct at the moment you may want to have a look at GNU Poke, still very much in the beginning phase it’s a language / editor / command line tool for pretty close to where you’re going. I suspect the language designers would be interested in any weird cases that you run across that it can’t handle :-)
Regards,
Cormac.
It’s worth noting that “stride” is a term in active use today in at least one language, Linden Scripting Language for Second Life…it doesn’t have multidimensional arrays, but it does have lists as a generalization of arrays – and some (but not all) functions for working with lists have a stride parameter.
“Stride” is also used in SPIR-V, the shader binary format used by OpenGL and Vulkan. It has largely the same meaning it does here.
ArrayStrideis the distance between two successive elements in an array.MatrixStrideis the distance between two successive rows in a row-major matrix or columns in a column-major matrix.XfbStrideis the distance between two successive vertices in a transform feedback buffer.I think ‘stride’ is common in bitmap descriptions, and the usage is directly analogous to Eric’s. Probably not a coincidence.
There’s a comment in the remarks section of https://docs.microsoft.com/en-us/windows/win32/api/wingdi/ns-wingdi-bitmapinfoheader that may be relevant in an example,
[quote]If there is padding in the image buffer, never dereference a pointer into the memory that has been reserved for the padding. If the image buffer has been allocated in video memory, the padding might not be readable memory.[/quote]
Can’t edit that, browser has scripting turned off. Sorry.
Damn cookies…
>I think ‘stride’ is common in bitmap descriptions, and the usage is directly analogous to Eric’s. Probably not a coincidence.
No, of course it isn’t a coincidence. I attributed the term in the OP.
Probably sometimes means obviously.
Anyway what piqued my interest was the explicit warning about the gap between the ‘singleton length’ and the stride in a context that’s reasonably relatable across platforms and OSes.