choose a bincode successor

[KonradHoeffner]

https://gemini.google.com/share/a46c1158645f

[KonradHoeffner]

The easiest one would probably be to switch to bincode-next, which is used by gungraun as well, however that is only a dev dependency, however rkyv could be faster.
But I also want to keep binary size and compile time as low as possible, so postcard looks like the best option as it's design goals include "Be resource efficient - memory usage, code size, developer time, and CPU time; in that order".

[KonradHoeffner]

Another option would be to actually downgrade bincode to 1.3.3 which is currently used by qwt so that one needs to be compiled anyways.

[GregHanson]

This crate is currently using bincode only for the cache file correct? I don't know if it helps this particular issue or if it is worth opening another issue for dedicated discussion - but could re-evaluating the cache file contents/format simplify or remove the bincode dependency?

The cache file currently contains the original HDT file's header length (bytes) followed by a full dump of the TriplesBitmap struct:

hdt/src/triples.rs

Line 317 in 42dcf27

let triples: TriplesBitmap = bincode::serde::decode_from_std_read(reader, bincode::config::standard())?;

hdt/src/hdt.rs

Line 200 in 42dcf27

bincode::serde::encode_into_std_write(triples, &mut writer, bincode::config::standard())?;

I have been playing around with variations of the cache file since I haven't been a big fan of dumping the entire TriplesBitmap struct (larger cache file) and instead only the wavelet_y from TriplesBitmap and the OPIndex bitmap+sequence and some offsets of various resources in the original HDT file (example POC here). Then qwt's wavelet struct becomes the only consumer/requirement for bincode - and I see that upstream qwt doesn't even need it as a requirement based on your PR here?

[KonradHoeffner]

Another option would be to actually downgrade bincode to 1.3.3 which is currently used by qwt so that one needs to be compiled anyways.

Turns out bincode is only used for tests and performance measurements scripts in qwt, so I submitted PR rossanoventurini/qwt#28 to move it to dev dependencies. Assuming this gets merged eventually, this argument in favor of bincode 1.3.3 no longer stands.

P.S.: Ah I just read your post that you found that already :-)

[KonradHoeffner]

This crate is currently using bincode only for the cache file correct? I don't know if it helps this particular issue or if it is worth opening another issue for dedicated discussion - but could re-evaluating the cache file contents/format simplify or remove the bincode dependency?

Correct, it's only used for the cache, let's continue using this issue for it.
I don't have any bincode experience other than merging your cache PR so I don't mind removing it without any replacements if that is possible :-)
I have used serialization a lot in Java so I like having a simple low maintenance solution that works out of the box but in Java you didn't need any additional libraries.
Also it seems like qwt still uses serde which can't be moved to dev dependencies as it provides the serialization interface, so we could not save on the serde dependency anyways.

Is your idea to implement a custom serde serializer or to move off of serde as well?

The cache file currently contains the original HDT file's header length (bytes) followed by a full dump of the TriplesBitmap struct:

hdt/src/triples.rs

Line 317 in 42dcf27
let triples: TriplesBitmap = bincode::serde::decode_from_std_read(reader, bincode::config::standard())?;

hdt/src/hdt.rs

Line 200 in 42dcf27
bincode::serde::encode_into_std_write(triples, &mut writer, bincode::config::standard())?;

I have been playing around with variations of the cache file since I haven't been a big fan of dumping the entire TriplesBitmap struct (larger cache file) and instead only the wavelet_y from TriplesBitmap and the OPIndex bitmap+sequence and some offsets of various resources in the original HDT file (example POC here). Then qwt's wavelet struct becomes the only consumer/requirement for bincode - and I see that upstream qwt doesn't even need it as a requirement based on your PR here?

OK this POC looks great but I would like to give my intuitive first impression on the various tradeoffs here, and would like to get your estimate / correction on those points:

1. We would still need to compile serde (qwt) but not bincode, thus we get faster compile times and smaller binaries.
2. Due to bincode being unmaintained this could also improve security in case there ever is some kind of security loophole detected in bincode.
3. The current way of encoding the current triplesbitmap with bincode is easy to maintain and understand for new contributors and if there is a change in TriplesBitmap we don't need to change anything in the code, other than upgrading the cache file extension to avoid getting errors (or even worse potentially silent errors) if a file gets read with a newer version of hdt but an older version of the cache file format.
4. On the other hand using your optimized implementation, we now have to maintain the serialization logic forever and whenever TriplesBitmap changes (which I guess is not often) to not forget to change the cache logic accordingly. This could increase barrier to entry. On the other hand, the index files would be smaller (I don't know how much) because only part of the triples bitmap is saved in the cache. Also the loading time could change (getting faster?).

Then there is also the the option of for example adopting postcard, which would avoid the security and other issues related to bincode being unmaintained but still keeps some of the other tradeoffs.

[KonradHoeffner]

Added cached and uncached HDT load benchmarks in ab5f48c which could be useful here.
Note that there is already an HDT load time and memory measurement as part of the comparative HDT library benchmark at https://github.com/KonradHoeffner/rdf_benchmark but that is more difficult to compare different branches with and more aimed at comparing stable versions.

P.S.: We also have a gungraun bench_load for the uncached case but I think gungraun is better suited to query benchmarks where cache hits and CPU cycles are more important than.

[KonradHoeffner]

persondata_en.hdt is only 86M in size but I don't want to add a larger one to the test/benchmark resources for now.

hdt$ cargo bench --bench criterion --all-features read_hdt           
    Finished `bench` profile [optimized] target(s) in 0.05s
     Running benches/criterion.rs (target/release/deps/criterion-2078f151a5d30243)
read_hdt/read_hdt_uncached
                        time:   [445.96 ms 447.25 ms 448.51 ms]
                        change: [−0.7817% −0.3314% +0.1291%] (p = 0.52 > 0.05)
                        No change in performance detected.
read_hdt/read_hdt_cached
                        time:   [68.298 ms 68.470 ms 68.631 ms]
                        change: [−3.4640% −0.8740% +1.8838%] (p = 0.69 > 0.05)
                        No change in performance detected.

[KonradHoeffner]

I'm not a fan of postcard, apparently it cannot read from a BufRead without either manually loading it into a buffer first or reserving a fixed size buffer, it also seems a lot slower.

let mut buffer = Vec::new();
let _ = reader.read_to_end(&mut buffer);
let triples: TriplesBitmap = postcard::from_bytes(&buffer)?;            

read_hdt/read_hdt_uncached
                        time:   [453.08 ms 455.87 ms 458.96 ms]
                        change: [+1.2175% +1.9285% +2.6145%] (p = 0.00 < 0.05)
                        Performance has regressed.
read_hdt/read_hdt_cached
                        time:   [79.252 ms 79.710 ms 80.325 ms]
                        change: [+15.814% +16.401% +17.038%] (p = 0.00 < 0.05)
                        Performance has regressed.

The generated libhdt.so from cargo build --all-features --releaseis 706kb in size in both cases.
persondata_en.hdt.index.v1-rust-cache is 80MB in size with bincode and 83MB in size with postcard.
Interestingly there is no error when using one with the cache file of the other, it just silently seems to notice that it's the wrong format and replaces it but I have to check the code again to make sure.

[KonradHoeffner]

As a next step I will try out rkyv but it seems to require more extensive refactoring that I can do today.

[KonradHoeffner]

Trying out rkyv in the branch of the same name but apparently this is not as easy as with postcard and bincode because all serialized types need to derive rkyv:Archive, which qwt datastructures do not do. There are apparently ways around that by going through byte vectors again but this defeats the purpose of using memmap2 and zero copy serialization.

[KonradHoeffner]

@GregHanson: Your POC is very interesting! I took the liberty to cherry pick the mownstr-commit for now and looked at the hybrid HdtAny implementation.
Did you already do some benchmarking on how it compares in RAM usage and query speed comparing the file backed and cached hybrid option vs the in-memory option?
Intuitively I would expect that the binary searches of some triple patterns would make efficient memory backed querying very difficult.
On the other hand this could yield massive RAM savings especially if multiple processes are opening the same HDT file in parallel.

From my experience with hosting research project artifacts in the form of ontologies and knowledge graphs, our typical long term publication setup is an RDF browser like RickView + a Virtuoso SPARQL endpoint. If the HDT SPARQL support matures out of the experimental stage and gets an added Virtuoso-like SPARQL API + human query interface, this could then be switched over to an HDT-based solution, meaning Semantic Web research project artifacts use less resources to maintain, hopefully leading to less costs, less missing functionality and longer uptime.

[KonradHoeffner]

P.S.: @GregHanson I noticed that the HdtAny enum approach causes lots of boilerplate / code duplication, was an HdtAny trait considered as well? In RickView there was a similar use case where I would have preferred trait objects but due to Sophia graphs not supporting that I had to use a more verbose enum based solution.

[GregHanson]

I took the liberty to cherry pick the mownstr-commit

No problems with that!

. . . looked at the hybrid HdtAny implementation.

I didn't think you'd be interested in any of that as it introduces a pretty big code change as well as a mix of unsafe's via memmap's! There are significant memory savings on the larger RDF datasets. Load times do speed up - but I guess I was only testing with my modified cache vs non-cache (and not the existing cache implementation). And yes there is a query slow down as files scale - so it's just a matter of tradeoffs. I can run the numbers of the existing pure in-memory vs hybrid approach using the qlever blog test cases and get back to you.

HdtAny enum approach causes lots of boilerplate / code duplication, was an HdtAny trait considered as well

No intentional design choices there, it's been awhile since I did the implementation and haven't had a chance to circle back to compare one over the other. I was probably trying to eliminate duplication for the sake of maintaining an easier patch with an enum but that's clearly no longer the case haha