Why is RSC string data word-aligned?
I'm returning to some of the code that deals with Oberon's RSC binary file format. The first time I went through this exercise, I noticed that ORG pads string data, so individual strings begin on word boundaries, and I didn't think much about it. Presumably it was done for efficiency. Now, though, I'm wondering. Does anyone have a breakdown comparing the two approaches--where strings don't get padded with NUL bytes and may begin anywhere, versus what happens if with word alignment? If there are some string handling routines where this makes a material difference, can someone point to them? I've already looked around, but I realize that string representation is a cross-cutting concern, and there's just too much material to exhaustively scour it all again. If there was a call out on this topic in the explanation of the the simple compiler that's documented in Compiler Construction, then I wasn't able to find it. I looked at a few sections in the Oberon book as well, hoping to see if it was explained (e.g. the module loader chapter), but didn't spot anything there, either. -- Colby Russell
Just an intuition, but if string constants and string variables start on a word boundary and are padded with nul to a word boundary then a number of string operations only require word access, simplifying assignment (copying) and comparison. On Sat, Jan 30, 2021 at 12:12 PM Colby Russell <oberon@x.colbyrussell.com> wrote:
I'm returning to some of the code that deals with Oberon's RSC binary file format. The first time I went through this exercise, I noticed that ORG pads string data, so individual strings begin on word boundaries, and I didn't think much about it. Presumably it was done for efficiency. Now, though, I'm wondering.
Does anyone have a breakdown comparing the two approaches--where strings don't get padded with NUL bytes and may begin anywhere, versus what happens if with word alignment? If there are some string handling routines where this makes a material difference, can someone point to them?
I've already looked around, but I realize that string representation is a cross-cutting concern, and there's just too much material to exhaustively scour it all again. If there was a call out on this topic in the explanation of the the simple compiler that's documented in Compiler Construction, then I wasn't able to find it. I looked at a few sections in the Oberon book as well, hoping to see if it was explained (e.g. the module loader chapter), but didn't spot anything there, either.
-- Colby Russell
-- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
Right. Look at ORG.CopyString then you know why….. Jörg From: Oberon <oberon-bounces@lists.inf.ethz.ch> On Behalf Of Charles Perkins Sent: Saturday, January 30, 2021 9:23 PM To: ETH Oberon and related systems <oberon@lists.inf.ethz.ch> Subject: Re: [Oberon] Why is RSC string data word-aligned? Just an intuition, but if string constants and string variables start on a word boundary and are padded with nul to a word boundary then a number of string operations only require word access, simplifying assignment (copying) and comparison. On Sat, Jan 30, 2021 at 12:12 PM Colby Russell <oberon@x.colbyrussell.com <mailto:oberon@x.colbyrussell.com> > wrote: I'm returning to some of the code that deals with Oberon's RSC binary file format. The first time I went through this exercise, I noticed that ORG pads string data, so individual strings begin on word boundaries, and I didn't think much about it. Presumably it was done for efficiency. Now, though, I'm wondering. Does anyone have a breakdown comparing the two approaches--where strings don't get padded with NUL bytes and may begin anywhere, versus what happens if with word alignment? If there are some string handling routines where this makes a material difference, can someone point to them? I've already looked around, but I realize that string representation is a cross-cutting concern, and there's just too much material to exhaustively scour it all again. If there was a call out on this topic in the explanation of the the simple compiler that's documented in Compiler Construction, then I wasn't able to find it. I looked at a few sections in the Oberon book as well, hoping to see if it was explained (e.g. the module loader chapter), but didn't spot anything there, either. -- Colby Russell -- Oberon@lists.inf.ethz.ch <mailto:Oberon@lists.inf.ethz.ch> mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
Copying my orginal response to Charles here, because I forgot to reply to the list. On 1/30/21 2:23 PM, Charles Perkins wrote:
if string constants and string variables start on a word boundary and are padded with nul to a word boundary then a number of string operations only require word access
That's my intuition as well, but that's what I'm trying to verify. I'm trying to track down some specific, concrete examples where we can see that the cost of not having padding is higher than the cost of dealing with a string with padding. Operations like printing a string, for example, are what I have in mind. If you have a 5-character string, word alignment means you can get the full contents in 2 memory accesses, but the operations are still going to be occurring at the byte level... So where are the savings? On 1/30/21 3:16 PM, Jörg wrote:
Right. Look at ORG.CopyString then you know why
ORG.CopyString operates on ORG `Item` objects representing in-memory strings, not the binary data contained within an RSC file. By the time the generated code is executing, the module's string section has already been read from disk by the module loader--which happens a single character at a time. Viz: <https://hypothes.is/a/Wx_nmmNEEeuHEi-6X3lPnQ> It appears this is an (unnoticed?) opportunity for further optimization of the Oberon system. The caveat being that it constitutes a breaking change to the RSC file format. So perhaps Wirth has noticed and just decided that it wasn't worth the trouble? -- Colby Russell
-----Original Message----- From: Oberon [mailto:oberon-bounces@lists.inf.ethz.ch] On Behalf Of Colby Russell Sent: Sunday, 31 January 2021 8:22 AM To: ETH Oberon and related systems; Jörg Subject: Re: [Oberon] Why is RSC string data word-aligned?
Copying my orginal response to Charles here, because I forgot to reply to the list.
On 1/30/21 2:23 PM, Charles Perkins wrote:
if string constants and string variables start on a word boundary and > are padded with nul to a word boundary then a number of string operations only require word access
That's my intuition as well, but that's what I'm trying to verify. I'm trying to track down some specific, concrete examples where we can see that the cost of not having padding is higher than the cost of dealing with a string with padding. Operations like printing a string, for example, are what I have in mind. If you have a 5- character string, word alignment means you can get the full contents in 2 memory accesses, but the operations are still going to be occurring at the byte level... So where are the savings?
On 1/30/21 3:16 PM, J rg wrote:
Right. Look at ORG.CopyString then you know why
ORG.CopyString operates on ORG `Item` objects representing in-memory strings, not the binary data contained within an RSC file. By the time the generated code is executing, the module's string section has already been read from disk by the module loader--which happens a single character at a time. Viz:
<https://hypothes.is/a/Wx_nmmNEEeuHEi-6X3lPnQ>
It appears this is an (unnoticed?) opportunity for further optimization of the Oberon system. The caveat being that it constitutes a breaking change to the RSC file format. So perhaps Wirth has noticed and just decided that it wasn't worth the trouble?
I checked a couple of the compiler modules (ORP and ORS) and the number of nulls in strings in the object file is about 1% of the total file size so I would agree that it is not worth the trouble. Regards, Chris Burrows CFB Software https://www.astrobe.com/RISC5
On 1/30/21 5:44 PM, Chris Burrows wrote:
Colby Russell Sent: Sunday, 31 January 2021 8:22 AM [...] <https://hypothes.is/a/Wx_nmmNEEeuHEi-6X3lPnQ>
It appears this is an (unnoticed?) opportunity for further optimization of the Oberon system. The caveat being that it constitutes a breaking change to the RSC file format. So perhaps Wirth has noticed and just decided that it wasn't worth the trouble?
I checked a couple of the compiler modules (ORP and ORS) and the number of nulls in strings in the object file is about 1% of the total file size
I don't mention is as a concern for file size, but as I mentioned in the Hypothesis annotation, as a matter of efficiency. The choice to align on word boundaries is (presumably) for reasons of efficiency. But by doing the alignment in the object file itself rather than in the module loader, whatever efficiency is sought is surely overwhelmed by the fact that many more cycles are wasted by the spurious character reads than the number of cycles saved, no? Every padding byte in the object file results in more time spent in the read loop and extra calls to `Files.Read`, slowing down the module loader. The fact that this situation (probably) arose out of trying to optimize for memory access could be an example of Knuth's adage that "premature optimization is the root of all evil"--many more cycles are wasted (including memory reads) than in the naive implementation where there was no attempt to optimize. -- Colby Russell
-----Original Message----- From: Colby Russell [mailto:oberon@x.colbyrussell.com] Sent: Sunday, 31 January 2021 10:55 AM To: chris@cfbsoftware.com; ETH Oberon and related systems Subject: Re: [Oberon] Why is RSC string data word-aligned?
On 1/30/21 5:44 PM, Chris Burrows wrote:
Colby Russell Sent: Sunday, 31 January 2021 8:22 AM [...] >> <https://hypothes.is/a/Wx_nmmNEEeuHEi-6X3lPnQ>
It appears this is an (unnoticed?) opportunity for further >> optimization of the Oberon system. The caveat being that it >> constitutes a breaking change to the RSC file format. So perhaps >> Wirth has noticed and just decided that it wasn't worth the trouble?
I checked a couple of the compiler modules (ORP and ORS) and the number of > nulls in strings in the object file is about 1% of the total file size
I don't mention is as a concern for file size, but as I mentioned in the Hypothesis annotation, as a matter of efficiency. The choice to align on word boundaries is (presumably) for reasons of efficiency. But by doing the alignment in the object file itself rather than in the module loader, whatever efficiency is sought is surely overwhelmed by the fact that many more cycles are wasted by the spurious character reads than the number of cycles saved, no? Every padding byte in the object file results in more time spent in the read loop and extra calls to `Files.Read`, slowing down the module loader.
Sure - I got that. However, the whole object file is read in when the module is loaded. Hence, the module loader is only slowed down by 1% because of those extra nulls. Even on my 25 MHz RISC5 system hardware, module loading appears to be instantaneous so any gain would not be noticeable. Remember also that in Project Oberon, a module only ever has to be loaded once between reboots unless you have manually unloaded it. Regards, Chris Burrows CFB Software https://www.astrobe.com/RISC5
On 1/30/21 7:19 PM, Chris Burrows wrote:
Sure - I got that. However, the whole object file is read in when the module is loaded. Hence, the module loader is only slowed down by 1% because of those extra nulls. Even on my 25 MHz RISC5 system hardware, module loading appears to be instantaneous so any gain would not be noticeable [...]
Chris, I understand what you're saying, but it's besides the point. It's not as if we're discussing code that's written in a "natural", naive way and I'm proposing a slightly more complicated strategy for the benefit of a micro-optimization. It's rather very much the opposite. The code as written is _complicated_ at the moment by an attempt at optimization by aligning to a word boundary--or at least that's my best guess for the reason that this strategy was chosen, and the gut feeling that everyone has responded with so far has agreed with this. What I'm discussing is *removing* the complication so that it uses a more "naive" strategy, and as a result actually ends up being _more_ efficient. I.e., nothing that I can see at this point nor any of the things brought up in response to my question are able to validate that this optimization pays for itself. As I wrote already, it's actually making things worse by any measure offered up 'til now. -- Colby Russell
Colby Strings in memory are word-aligned as string assignments can be done 4 times faster than byte-access. As drawback of this decision, we might have some superfluous consecutive 0X. Now, do I understand you correctly that while writing the rsc file you want to compress consecutive 0X to only one 0X? Do you really want to compress the string area while writing to (huge) disk, where normally space is no issue? To optimize the File IO you would turn this Files.WriteInt(R, strx); FOR i:= 0 TO strx-1 DO Files.Write(str[i]) END; into something like this eos := FALSE; FOR i := 0 TO strx-1 DO IF str[i] = 0X THEN eos := TRUE ELSE IF eos THEN Files.Write(R, 0X) END; Files.Write(R, str[i]); eos := FALSE END END; Files.Write(R, 0X); BTW: There is a reason why strings are written byte-wise although they are word-aligned. It has to do with endianness. The endianess is not defined in the Oberon system, as it doesn‘t matter as long as you don‘t leave the system, eg by writing to files. If the compiler would write strings as words (it could do that as strings are word-aligned) the writing and reading system must have the same endianess. As strings are written byte by byte, the possibly different endianesses of the reading and writing systems do not matter. br Jörg
Am 31.01.2021 um 00:46 schrieb Chris Burrows <chris@cfbsoftware.com>:
-----Original Message----- From: Oberon [mailto:oberon-bounces@lists.inf.ethz.ch] On Behalf Of Colby Russell Sent: Sunday, 31 January 2021 8:22 AM To: ETH Oberon and related systems; Jörg Subject: Re: [Oberon] Why is RSC string data word-aligned?
Copying my orginal response to Charles here, because I forgot to reply to the list.
On 1/30/21 2:23 PM, Charles Perkins wrote: if string constants and string variables start on a word boundary and > are padded with nul to a word boundary then a number of string operations only require word access
That's my intuition as well, but that's what I'm trying to verify. I'm trying to track down some specific, concrete examples where we can see that the cost of not having padding is higher than the cost of dealing with a string with padding. Operations like printing a string, for example, are what I have in mind. If you have a 5- character string, word alignment means you can get the full contents in 2 memory accesses, but the operations are still going to be occurring at the byte level... So where are the savings?
On 1/30/21 3:16 PM, J rg wrote: Right. Look at ORG.CopyString then you know why
ORG.CopyString operates on ORG `Item` objects representing in-memory strings, not the binary data contained within an RSC file. By the time the generated code is executing, the module's string section has already been read from disk by the module loader--which happens a single character at a time. Viz:
<https://hypothes.is/a/Wx_nmmNEEeuHEi-6X3lPnQ>
It appears this is an (unnoticed?) opportunity for further optimization of the Oberon system. The caveat being that it constitutes a breaking change to the RSC file format. So perhaps Wirth has noticed and just decided that it wasn't worth the trouble?
I checked a couple of the compiler modules (ORP and ORS) and the number of nulls in strings in the object file is about 1% of the total file size so I would agree that it is not worth the trouble.
Regards, Chris Burrows CFB Software https://www.astrobe.com/RISC5
-- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
On 1/30/21 6:50 PM, Joerg wrote:
Now, do I understand you correctly that while writing the rsc file you want to compress consecutive 0X to only one 0X? Do you really want to compress the string area while writing to (huge) disk, where normally space is no issue?
To optimize the File IO you would turn this [...] into something like
No. To repeat: I'm talking about CPU instructions and memory reads--i.e. trying to measure this "optimization" on the terms that were presumably a concern at the time the strategy was chosen--not an attempt to optimize for disk space. this I'm not sure where that sample comes from. It doesn't match the code in the module loader (and it wouldn't make sense; the module loader is doing a file read, not a write).
As strings are written byte by byte, the possibly different endianesses of the reading and writing systems do not matter.
Right, this reinforces what I'm referring to. When dealing with strings, operations are going to occur on a character-by-character, anyway, due to external constraints involving the nature of strings--as in the section of the module loader that I linked to, and as you're describing now. So again: in concrete terms, where does the efficiency for word alignment come in? In trying to reason about the strategy, I've _only_ found downsides so far. -- Colby Russell
Hi Colby,
... So again: in concrete terms, where does the efficiency for [string] word alignment come in?
String assignment (as has been pointed out). The code generated by ORG.CopyString moves string data around by words, filling the full 32-bits of a register buffer with string data on each loop iteration. This may happen many times over and over again as code is running, once a module is loaded into memory. The unaligned data in a .rsc file is, I agree, unfortunate, as it could have been aligned relatively easily and then data could have been copied into memory a word at a time. But module loading only happens once, and there's lots of other stuff to do too, so as you say it was likely deemed not worth it. HTH, Paul
I thought Colby does agree that strings have to be word-aligned a) IN MEMORY, because of 4 times faster string assignment (s := “Hi there“;) and 4 times faster string parameter passing to procedures. (Out.String(“Hi there“);) see ORG.CopyString. Word-alignment is not needed for string comparison (IF s = „“Hi there“ THEN) see ORG.StringRelation. I understood he wondered why the strings are word-aligned b) IN RSC FILES too because the loader could do it while reading. Colby, do I summarize your request correctly? If so, let me explain what would have to be done to make strings NOT word-aligned in rsc files. First, lets remember that a module has a compile time TC and later on the load time TL. It’s not enough to have the word-alignment at TL only. As the compiler generates code for fast string assignments, the compiler needs to know the word-aligned offset of a string at TC already. Therefore, the variable „strx“ keeping track of the string offset in ORG is always word-aligned (see ORG.MakeStringItem) Principally, Colby is right, we could now decide to break the rule of word-alignment between TC and TL. That can be done as follows: - the compiler optimizes the file IO (and hence the file size but not necessarily the CPU cycles) at TC by writing the string buffer without consecutive 0X. - the loader could re-word-align the string buffer at TL. Could be done but I doubt 1) that the code is easier to read, 2) the file IO gain is noticeable 3) it‘s worth the effort. br Jörg
Am 31.01.2021 um 08:44 schrieb Paul Reed <paulreed@paddedcell.com>:
Hi Colby,
... So again: in concrete terms, where does the efficiency for [string] word alignment come in?
String assignment (as has been pointed out). The code generated by ORG.CopyString moves string data around by words, filling the full 32-bits of a register buffer with string data on each loop iteration. This may happen many times over and over again as code is running, once a module is loaded into memory.
The unaligned data in a .rsc file is, I agree, unfortunate, as it could have been aligned relatively easily and then data could have been copied into memory a word at a time. But module loading only happens once, and there's lots of other stuff to do too, so as you say it was likely deemed not worth it.
HTH, Paul -- Oberon@lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon
participants (6)
-
Charles Perkins -
Chris Burrows -
Colby Russell -
Joerg -
Jörg
-
Paul Reed