On Sat, 19 Jan 2019 00:45:27 -0800, Walter Bright wrote:
> Andrei and I were talking on the phone today, trading ideas about speeding up importation of Phobos files. Any particular D file tends to import much of Phobos, and much of Phobos imports the rest of it. We've both noticed that file size doesn't seem to matter much for importation speed, but file lookups remain slow.
> 
> So looking up fewer files would make it faster.

I compiled one file with one extra -I directive as a test. The file had two imports, one for url.d (which depends on std.conv and std.string) and one for std.stdio.

For each transitive import encountered, the compiler:
* looked at each import path (total of four: ., druntime, phobos, and
urld's source dir)
* looked at each possible extension (.d, .di, and none)
* built a matching filename
* checked if it existed

Maybe it should do a shallow directory listing for the current directory and every -I path at startup, using that information to prune the list of checks it needs to do. It could also do that recursively when importing from a subpackage. Then it would have called 'opendir' about four times and readdir() about 70 times; it wouldn't ever have had to call exists(). It would allocate a lot less memory. And that's a change that will help people who don't zip up their source code every time they want to compile it.

It could even do this in another thread while parsing the files passed on the command line. That would require a bit of caution, of course.

On Sat, Jan 19, 2019 at 06:05:13PM +0000, Neia Neutuladh via Digitalmars-d wrote: [...]
> I compiled one file with one extra -I directive as a test. The file had two imports, one for url.d (which depends on std.conv and std.string) and one for std.stdio.
> 
> For each transitive import encountered, the compiler:
> * looked at each import path (total of four: ., druntime, phobos, and
> urld's source dir)
> * looked at each possible extension (.d, .di, and none)
> * built a matching filename
> * checked if it existed
> 
> Maybe it should do a shallow directory listing for the current directory and every -I path at startup, using that information to prune the list of checks it needs to do. It could also do that recursively when importing from a subpackage. Then it would have called 'opendir' about four times and readdir() about 70 times; it wouldn't ever have had to call exists().  It would allocate a lot less memory. And that's a change that will help people who don't zip up their source code every time they want to compile it.
[...]

Excellent finding! I *knew* something was off when looking up a file is more expensive than reading it.  I'm thinking a quick fix could be to just cache the intermediate results of each lookup, and reuse those instead of issuing another call to opendir() each time.  I surmise that after this change, this issue may no longer even be a problem anymore.


T

-- 
It is of the new things that men tire --- of fashions and proposals and improvements and change. It is the old things that startle and intoxicate. It is the old things that are young. -- G.K. Chesterton

On Sat, 19 Jan 2019 11:56:29 -0800, H. S. Teoh wrote:
> Excellent finding! I *knew* something was off when looking up a file is more expensive than reading it.  I'm thinking a quick fix could be to just cache the intermediate results of each lookup, and reuse those instead of issuing another call to opendir() each time.  I surmise that after this change, this issue may no longer even be a problem anymore.

It doesn't even call opendir(). It assembles each potential path and calls exists(). Which might be better for only having a small number of imports, but that's not the common case.

I've a partial fix for Posix, and I'll see about getting dev tools running in WINE to get a Windows version. (Which isn't exactly the same, but if I find a difference in FindFirstFile / FindNextFile between Windows and WINE, I'll be surprised.)

I'm not sure what it should do when the same module is found in multiple locations, though -- the current code seems to take the first match. I'm also not sure whether it should be lazy or not.

Also symlinks and case-insensitive filesystems are annoying.

https://github.com/dhasenan/dmd/tree/fasterimport

On Saturday, 19 January 2019 at 20:32:07 UTC, Neia Neutuladh wrote:
>
> Also symlinks and case-insensitive filesystems are annoying.
>
> https://github.com/dhasenan/dmd/tree/fasterimport

Considering it's only ever used in one place it's not a canidate for root.
Maybe you could just put it in src.

On Saturday, 19 January 2019 at 15:25:37 UTC, Boris-Barboris wrote:
> On Saturday, 19 January 2019 at 08:45:27 UTC, Walter Bright wrote:
>> Andrei and I were talking on the phone today, trading ideas about speeding up importation of Phobos files. Any particular D file tends to import much of Phobos, and much of Phobos imports the rest of it. We've both noticed that file size doesn't seem to matter much for importation speed, but file lookups remain slow.
>>
>> So looking up fewer files would make it faster.
>
> Sounds rather strange that on modern operating systems, that cache files themselves and the metadata even more surely (VFS directory cache as an example), file lookup is a problem.
>
> Calls to something like glob(3) could render the whole phobos directory tree to your memory in milliseconds.

It's a known problem that Windows can't cache file metadata as aggressively as Posix systems because of differences in filesystem semantics.  (See https://github.com/Microsoft/WSL/issues/873#issuecomment-425272829)

Walter did say he saw benchmarked improvements on Linux for Warp, though.

On Saturday, 19 January 2019 at 08:45:27 UTC, Walter Bright wrote:
> We've both noticed that file size doesn't seem to matter much for importation speed, but file lookups remain slow.

Maybe there are still some tricks to apply to make the lookup faster?
Ripgrep [1] is to my knowledge the fastest grepping tool out there currently and the speed is mostly about grepping probably but to be fast they need to get to the files fast too. So it might be helpful to look at the code.

[1] https://github.com/BurntSushi/ripgrep

On 1/19/19 3:32 PM, Neia Neutuladh wrote:
> On Sat, 19 Jan 2019 11:56:29 -0800, H. S. Teoh wrote:
>> Excellent finding! I *knew* something was off when looking up a file is
>> more expensive than reading it.  I'm thinking a quick fix could be to
>> just cache the intermediate results of each lookup, and reuse those
>> instead of issuing another call to opendir() each time.  I surmise that
>> after this change, this issue may no longer even be a problem anymore.
> 
> It doesn't even call opendir(). It assembles each potential path and calls
> exists(). Which might be better for only having a small number of imports,
> but that's not the common case.
> 
> I've a partial fix for Posix, and I'll see about getting dev tools running
> in WINE to get a Windows version. (Which isn't exactly the same, but if I
> find a difference in FindFirstFile / FindNextFile between Windows and
> WINE, I'll be surprised.)
> 
> I'm not sure what it should do when the same module is found in multiple
> locations, though -- the current code seems to take the first match. I'm
> also not sure whether it should be lazy or not.
> 
> Also symlinks and case-insensitive filesystems are annoying.
> 
> https://github.com/dhasenan/dmd/tree/fasterimport

This is great, looking forward to seeing this improvement merged. (There are packaging- and distribution-related advantages to archives independent of this.)

On Sunday, 20 January 2019 at 15:10:58 UTC, Andrei Alexandrescu wrote:
> On 1/19/19 3:32 PM, Neia Neutuladh wrote:
>> [...]
>
> This is great, looking forward to seeing this improvement merged. (There are packaging- and distribution-related advantages to archives independent of this.)

Andrei,
   Are you envisioning something like the JAR format Java uses? That would be pretty convenient for D library installation and imports...

-Doc

On 1/20/2019 9:53 AM, Doc Andrew wrote:
>     Are you envisioning something like the JAR format Java uses?

jar/zip/arc/tar/lib/ar/cab/lzh/whatever

They're all the same under the hood - a bunch of files concatenated together with a table of contents.

On Saturday, 19 January 2019 at 16:30:39 UTC, Andrei Alexandrescu wrote:
> On 1/19/19 4:12 AM, FeepingCreature wrote:
>> On Saturday, 19 January 2019 at 09:08:00 UTC, Walter Bright wrote:
>>> On 1/19/2019 1:00 AM, Temtaime wrote:
>>>> C'mon, everyone has a SSD, OS tends to cache previously opened files. What's the problem ?
>>>> Better speedup compilation speed.
>>>
>>> You'd think that'd be true, but it isn't. File reads are fast, but file lookups are slow. Searching for a file along a path is particularly slow.
>> 
>> If you've benchmarked this, could you please post your benchmark source so people can reproduce it? Probably be good to gather data from more than one PC. Maybe make a minisurvey for the results.
>
> I've done a bunch of measurements while I was working on https://github.com/dlang/DIPs/blob/master/DIPs/DIP1005.md, on a modern machine with SSD and Linux (which aggressively caches file contents). I don't think I still have the code, but it shouldn't be difficult to sit down and produce some. The overall conclusion of those experiments was that if you want to improve compilation speed, you need to minimize the number of files opened; once opened, whether it was 1 KB or 100 KB made virtually no difference.
>
> One thing I didn't measure was whether opening the file was most overhead, or closing also had a large share.

I deal with large compressed files. For large data lz4 would probably be a better choice over zip these days. And, even with cached lookups of dir entries, I think one file that is sequentially read will always be an improvement. Note also that compressed files may even be faster than uncompressed ones with some system configurations (relatively slow disk IO, many processors).

Another thing to look at is indexed compressed files. For example http://www.htslib.org/doc/tabix.html. Using those we may partition phobos into sensible sub-sections. Particularly section out those submodules people hardly ever use.