This PR https://github.com/dlang/dmd/pull/15199 reduces its size by 8 bytes, resulting in about 20Mb of memory savings compiling druntime, according to @dkorpel.

It is currently:

struct Loc
{
  uint linnum; // line number, starting from 1
  ushort charnum; // utf8 code unit index relative to start of line, starting from 1
  ushort fileIndex; // index into filenames[], starting from 1 (0 means no filename)
}

which is 8 bytes.

If it was 4 bytes, it could still store 4 billion unique locations, which ought to be enough for everyone. I toyed around with various encodings:

 6 bits for column - 1..64
15 bits for line - 1..32768
11 bits for file - 2047

I also thought of schemes like having the sign bit set an alternate encoding scheme.

So, for great glory, can anyone come up with a clever scheme that uses only 32 bits?

On Tuesday, 9 May 2023 at 00:24:44 UTC, Walter Bright wrote:
>  6 bits for column - 1..64
> 15 bits for line - 1..32768
> 11 bits for file - 2047
>
> So, for great glory, can anyone come up with a clever scheme that uses only 32 bits?

I wouldn't separate out column/line/file at all. Concatenate all the files together in memory and store only an offset into that gigantic array. If an error happens, then and only then go back to extract the details by slicing the filename out of a listing and rescanning it to determine line and column. (You'd probably have an index that does a bit of both, like every new file or every 5000 lines, add an entry to the lookup table. Then when you do hit an error, you just need to scan from the closest point forward instead of the whole thing.)

If there's no errors, it uses little memory and is fast. If there is an error, the rescanning time is not significant anyway relative to the time to fix the error.

On 5/8/2023 5:32 PM, Adam D Ruppe wrote:
> I wouldn't separate out column/line/file at all. Concatenate all the files together in memory and store only an offset into that gigantic array. If an error happens, then and only then go back to extract the details by slicing the filename out of a listing and rescanning it to determine line and column. (You'd probably have an index that does a bit of both, like every new file or every 5000 lines, add an entry to the lookup table. Then when you do hit an error, you just need to scan from the closest point forward instead of the whole thing.)
> 
> If there's no errors, it uses little memory and is fast. If there is an error, the rescanning time is not significant anyway relative to the time to fix the error.

That is indeed a clever idea, thank you.

On 5/8/2023 6:41 PM, zjh wrote:
> 8 bits for columns - 1..256
> 15 bits for lines - 1..32768
> 9 bits for files - 512
> 
> 64 for column are generally not enough. After the above changes, the general projects are sufficient.
> But for large projects, there should be a switch, which needs to be expanded to '8' bytes.


I don't think 512 files is enough. As for columns, those aren't very important, and it can just "top out" at 64. Not perfect.

On 5/8/2023 5:32 PM, Adam D Ruppe wrote:
> I wouldn't separate out column/line/file at all. Concatenate all the files together in memory and store only an offset into that gigantic array. If an error happens, then and only then go back to extract the details by slicing the filename out of a listing and rescanning it to determine line and column. (You'd probably have an index that does a bit of both, like every new file or every 5000 lines, add an entry to the lookup table. Then when you do hit an error, you just need to scan from the closest point forward instead of the whole thing.)
> 
> If there's no errors, it uses little memory and is fast. If there is an error, the rescanning time is not significant anyway relative to the time to fix the error.

Thinking about it a bit more, it isn't necessary to concatenate the files at all. Just, for each file, record the starting line number, which would be the sum of all the lines in the files previously parsed.

Then, the line number can be converted to file/line by looking up the range of line numbers it falls in, which gives the file, and subtracting the corresponding starting line number, which gives the line.

So if we leave 8 bits for column, 1..256, that gives 24 for the line number, which gives room for 16,777,216 lines which ought to be enough, and no rescanning necessary.

On Tuesday, 9 May 2023 at 00:24:44 UTC, Walter Bright wrote:
> This PR https://github.com/dlang/dmd/pull/15199 reduces its size by 8 bytes, resulting in about 20Mb of memory savings compiling druntime, according to @dkorpel.
>
> [...]
>
> So, for great glory, can anyone come up with a clever scheme that uses only 32 bits?

Yes, call me a madlad but in styx the filename information is in the DMD equivalent of `Scope` (and the Loc is 2*32 bits, {line,col}). If you do the same in DMD you can reduce the size to 32 bits, i.e 2*16 bits, {line,col}.

I'm not sure this would work for DMD but for styx the rationale was

1. in DMD the size of Loc is a known problem, that's why it's usually recommended to pass its instances by ref, let's not have the same problem.
2. there's much less Scopes than Loc.