Memory optimizations on larger HDT files

[GregHanson]

What new feature do you want?

To my understanding, calls to hdt::Hdt::new() read the entire HDT file into memory (header, dictionary, triples) and all operations performed on the HDT file afterwards are performed over that in-memory data model? If so, have there been any design considerations on how the source HDT file could create a memory-mapped view of the file starting from the triples section offset?

For context, I'm working on integrating the HDT library with oxigraph (oxigraph/oxigraph#1087). On larger datasets there is a significant overhead on the initial call to hdt::Hdt::new(). For instance running against a dump of DBLP (~500 million triples):

[DEBUG hdt::triples] Building wavelet matrix...
[DEBUG hdt::triples] Building OPS index...
[DEBUG hdt::triples] Built wavelet matrix with length 365063110
[DEBUG hdt::triples] built OPS index
[DEBUG hdt::hdt] HDT size in memory 5.9 GB, details:
[DEBUG hdt::hdt] Hdt {
        dict: FourSectDict {
            shared: total size 265.1 MB, 56011771 strings, sequence 12.3 MB with 3500737 entries, 28 bits per entry, packed data 252.9 MB,
            subjects: total size 292.0 KB, 41119 strings, sequence 6.1 KB with 2571 entries, 19 bits per entry, packed data 285.9 KB,
            predicates: total size 1.3 KB, 90 strings, sequence 16 B with 7 entries, 11 bits per entry, packed data 1.3 KB,
            objects: total size 1.5 GB, 56297252 strings, sequence 13.6 MB with 3518580 entries, 31 bits per entry, packed data 1.5 GB,
        },
        triples: total size 4.1 GB
        adjlist_z AdjList {
            sequence: 1.8 GB with 490171629 entries, 29 bits per entry,
            bitmap: 79.4 MB,
        }
        op_index total size 1.9 GB {
            sequence: 1.8 GB with 29 bits,
            bitmap: 76.6 MB
        }
        wavelet_y 419.3 MB,
    }
Load Time: 169.108882004s

About 6GB memory is used and if multiple HDT files of similar size are loaded, that memory consumption starts to become unwieldy - with a database choosing to either keep files loaded into memory or deal with the longer response times.

[KonradHoeffner]

Hi, loading memory overhead is indeed a pain point and has been the target of a lot of profiling and optimization, for example see issues #11 and #16.

It's especially problematic on Linux servers with low amounts of RAM that don't have swap space enabled, as the out of memory killer tends to just kill the process that is using most memory, in this case the application using the HDT library, without warning. Even if Docker is used and automatic restart is enabled that is far from desirable behavior for a server application.

Using memory mapping at the start could help prevent that spike. Or do you mean you want to use memory mapping the whole time, not just for the loading part?
Especially if you want to include databases and map memory to files after loading, this is outside of the bounds of what this simple library is intended for.
But generally my intuition is that if we add too many features that move into the direction of a full fledged SPARQL endpoint like Virtuoso, then at that point Virtuoso is probably better at that.
So to answer your question directly, at least I have thought about it but not given any design considerations on actually doing it.
However it is possible that @timplication, who did all the hard work of the initial work on this library, has a different take on this.

Also I have no experience with file-to-memory-mapping in Rust and I'm not sure how fast it would be, as many of the operations use binary search and thus random access, which memory is much better at than storage devices. However as most devices have moved from away from hard drives a long time ago, and binary search has logarithmic time complexity, it could not be that much of a problem depending on the type of triple pattern used.

At the end of the day I'm open to discussions about it and to try it out, especially if this is something that is easy to add and doesn't require a complete overhaul. However I'm not sure when I will find the time.

[KonradHoeffner]

P.S.: I am skeptical on how well caching works in this case, because for example the dictionary groups terms together that are similar instead of based on locality.
So I could imagine the file accesses being all over the place and the block-based storage caching not helping much but that would be interesting to be tested.

[timplication]

I don't know if memory mapping is going to make much sense because you want to pin the header and dictionary in memory all the time while streaming in the triples (you need that info in order to decode), and I am not sure whether the operating system allows you to do pinning like that (see Crotty et al., CIDR 2022).

I guess what could be done is allocate some buffer of predefined size that users can configure with a constant, load in the header + dict, and then populate that predefined buffer using as much triples as that buffer can handle. Then drop those triples and load in the next batch. Rinse and repeat on every .next() call. I'll see if I have some time to implement a basic version, but might take a while.

[KonradHoeffner]

Interestingly, the Java implementation of HDT seems to support memory mapping:

You can also use HDTManager.mapHDT() and HDTManager.mapIndexedHDT() to map the file instead of loading everything into main memory. The main advantage is that it requires much less memory, as it loads the data from disk on-demand, and therefore allows loading files even bigger than the machine’s main memory. It also allows the Operating System to keep the fragments cached even after closing the application. This results in faster initial loading time, and even allows several processes to access the same HDT file without having multiple copies in memory. The disadvantage is that searches can be slower, especially the first ones and/or when the system does not have much free memory to cache the read blocks.

A question issue response also explains:

There are two methods for loading HDTs; load (Creates Java arrays and copies the raw HDT), and map (Uses mmap from the OS underneath). Bitmaps are critical so they are always kept in memory, the rest of the data structures are just mapped and the operating system will load and keep in memory blocks (typically 4k bytes) using OS-specific policies. The more you use the HDT, the more memory you have, and the less other processess need the memory, the more data will be in RAM and faster will queries be.

[timplication]

Ok, so I don't have more time to look at this today. But the most common way to use mmap from Rust seems to be this library: memmap2-rs. There is however a huge disclaimer around that library since it is inherently unsafe to provide a &[u8] interface to a raw file that may be changed by other processes, and we cannot guarantee a &mut [u8] would have only one owner either. The TL;DR is that a file can be changed by other processes while you are using it, violating the contract that any mutable or immutable borrow needs to uphold, and we have no way to prevent other processes from accessing the file. As such if we provide this feature we have to probably feature-gate it and provide users with an unsafe constructor giving them an HdtMmap structure. And then it's the users' problem to ensure nobody writes to that specific HDT file while running this library. This seems very unidiomatic Rust me and there is likely a better solution.

Furthermore, I'm looking at the internal structure of the library again and everything takes a stateful BufReader positioned at the correct position in the file. So to work this feature into the library will probably constitute some significant refactoring. I'll make a new issue for this soon, linking to this one.

[GregHanson]

Thanks for the comments @timplication @KonradHoeffner

So to work this feature into the library will probably constitute some significant refactoring.

That was my impression too after reviewing the library

And then it's the users' problem to ensure nobody writes to that specific HDT file while running this library. This seems very unidiomatic Rust me and there is likely a better solution.

Agree, but this doesn't seem too big a change in direction from the library's original implementation. The README clearly states that the HDT file / RDF graph cannot be updated once loaded into memory, so personally we've been treating the input HDT files we load into the library as immutable and read-only. So I feel the spirit/functionality of this approach wouldn't change what the library already provides.

Some additional links for discussion for anyone else finding their way to this issue

• link 1

have to probably feature-gate it and provide users with an unsafe constructor giving them an HdtMmap structure.

Seems like the correct approach - though I guess I don't have any experience with other libraries using unsafe to know for sure if that aligns with any pre-established SOP

[GregHanson]

@KonradHoeffner Not sure if this it's worthy of a separate issue but I had another idea/question that also revolves around performance. Is there a potential benefit to exporting the index that gets created during the initial load so that subsequent loads of the same HDT file load faster? I know the https://github.com/rdfhdt rdf2hdt C implementation library supports building a pre-calculated hdt.index.v1-1 file during the conversion.

I'm still investigating the differences between what the rdf2hdt library includes in the index and this library's implementation - but I'm assuming the two types of indexes are not a 1:1 match (i.e. the index file produced in the C library is not something that can be consumed in this one without significant refactoring). I might defer to @timplication if he is aware of the specific differences between the two.

Just for some example data, using the DBLP dataset I linked in the original issue description:

-rw-rw-r--  1 ubuntu ubuntu 3.7G Jan  8 14:43 dblp.hdt
-rw-rw-r--  1 ubuntu ubuntu 3.0G Jan  8 14:53 dblp.hdt.index.v1-1

This HDT library takes a little under 3 minutes to load the hdt file:

[DEBUG hdt::hdt] HDT size in memory 5.9 GB, details:
[DEBUG hdt::hdt] Hdt {
        dict: FourSectDict {
            shared: total size 265.1 MB, 56011771 strings, sequence 12.3 MB with 3500737 entries, 28 bits per entry, packed data 252.9 MB,
            subjects: total size 292.0 KB, 41119 strings, sequence 6.1 KB with 2571 entries, 19 bits per entry, packed data 285.9 KB,
            predicates: total size 1.3 KB, 90 strings, sequence 16 B with 7 entries, 11 bits per entry, packed data 1.3 KB,
            objects: total size 1.5 GB, 56297252 strings, sequence 13.6 MB with 3518580 entries, 31 bits per entry, packed data 1.5 GB,
        },
        triples: total size 4.1 GB
        adjlist_z AdjList {
            sequence: 1.8 GB with 490171629 entries, 29 bits per entry,
            bitmap: 79.4 MB,
        }
        op_index total size 1.9 GB {
            sequence: 1.8 GB with 29 bits,
            bitmap: 76.6 MB
        }
        wavelet_y 419.3 MB,
    }
Load Time: 169.108882004s

When hdtSearch utilizes the index, it is ready to go in approximately a second

hdtSearch.mp4

It is worth highlighting that without a pre-calculated index file, hdtSearch builds its index significantly slower than this library, taking almost 12 minutes:

./hdtSearch engine/dblp.hdt
Predicate Bitmap in 15 sec 117 ms 220 us%
Count predicates in 1 min 35 sec 318 ms 12 us34.297 %
Count Objects in 29 sec 314 ms 917 us Max was: 25397356
Bitmap in 2 sec 723 ms 616 us5 % / 48.467 %
Bitmap bits: 490171629 Ones: 112309023
Object references in 3 min 46 sec 467 ms 675 us3 %
Sort lists in 5 min 25 sec 698 ms 203 us
Index generated in 11 min 34 sec 639 ms 732 us

[KonradHoeffner]

Is there a potential benefit to exporting the index that gets created during the initial load so that subsequent loads of the same HDT file load faster? I know the https://github.com/rdfhdt rdf2hdt C implementation library supports building a pre-calculated hdt.index.v1-1 file during the conversion.

Very good question, and there is absolutely a huge potential benefit!
The large differences in loading times is why in https://github.com/konradHoeffner/rdf_benchmark, I delete the index files after every run to get comparable results for the loading time benchmark among the HDT libraries (maybe I should add another graph with index files to show this huge benefit).
To be honest I just haven't had the need in my own projects (using it mostly for the RickView RDF browser which loads the file once and then runs for weeks on end) but if this would be helpful to you than I can take a look at it.
Or maybe @timplication is interested in doing it?
On first thought it seems like it wouldn't be that complicated to implement, even though it might not conform to the official index format it could still be useful as a cache.

[GregHanson]

Definitely interested, pending analysis of any memory consumption/time tradeoffs. I am worried a large portion of the initial load time of the HDT file is still going to be spent loading all the triples into memory - but maybe I am wrong on that assumption.

Which objects/data do you envision saving in the cached index? The rdfhdt library (link) saves:

• bitmapIndex
• arrayIndex
• predicate index
• predicate count

What would be the equivalent in this library? Everything in TriplesBitmap?

• order: Order
• bitmap_y: Bitmap,
• adjlist_z: AdjList,
• op_index: OpIndex,
• wavelet_y: WaveletMatrix,

If you think it's just a matter of serializing it to a file and loading the cached data if it exists, I would be willing to take a stab at a first pass implementation to get some preliminary data for comparison.

[GregHanson]

I made a first pass at the implementation. Just some custom Serialize/Deserialize functions for TriplesBitmap, diff here:
GregHanson@b065a66

First pass just leverages serde and bincode crates for saving/reading the cache file.

Using the DBLP again as an example, what took almost 3 minutes to load, now takes only 40 seconds (cold), and 10 second when reusing some caches:

$ sudo bash -c "sync; sleep 5; echo 3 > /proc/sys/vm/drop_caches"
$ ./de3 query -d engine/dblp.hdt --sparql XXX
Load Time: 44.800688389s
$ ./de3 query -d engine/dblp.hdt --sparql XXX
Load Time: 10.337962874s

Still not as quick of a load time as the C hdtSearch lib, but some improvement

And for some comparisons on index sizes:

-rw-rw-r--  1 ubuntu ubuntu 3.7G Jan  8 14:43 dblp.hdt                      # BASE
-rw-rw-r--  1 ubuntu ubuntu 3.0G Jan 28 17:21 dblp.hdt.index.v1-1           # C INDEX
-rw-rw-r--  1 ubuntu ubuntu 3.9G Jan 29 18:58 dblp.hdt.index.v1-rust-cache  # CUSTOM INDEX

It's larger than the base HDT file and the C based index file, but I have made zero optimizations on storing the underlying TriplesBitmap struct to file other than using the bincode crate - so I would imagine there be room for improvements there.

Also not sure how serde performs deserializing larger files in comparison to to any other crates so might be room for improvement there as well.

I have a larger dataset for wikipedia that I'm running now to see how that compares