vigna / webgraph-rs

A Rust port of the WebGraph framework

WebGraph

A Rust implementation of the WebGraph framework for graph compression.

WebGraph is a framework for graph compression aimed at studying web graphs, but currently being applied to several other type of graphs. It provides simple ways to manage very large graphs, exploiting modern compression techniques. More precisely, it is currently made of:

• A set of simple codes, called ζ codes, which are particularly suitable for storing web graphs (or, in general, integers with a power-law distribution in a certain exponent range).

• Algorithms for compressing web graphs that exploit gap compression and differential compression (à la LINK), intervalisation, and ζ codes to provide a high compression ratio (see our datasets). The algorithms are controlled by several parameters, which provide different tradeoffs between access speed and compression ratio.

• Algorithms for accessing a compressed graph without actually decompressing it, using lazy techniques that delay the decompression until it is actually necessary.

• Algorithms for analysing very large graphs, such as {@link it.unimi.dsi.webgraph.algo.HyperBall}, which has been used to show that Facebook has just four degrees of separation.

• A Java implementation of the algorithms above, now in maintenance mode.

• This crate, providing a complete, documented implementation of the algorithms above in Rust. It is free software distributed under either the GNU Lesser General Public License 2.1+ or the Apache Software License 2.0.

• Data sets for large graph (e.g., billions of links).

Citation

You are welcome to use and improve WebGraph for your research work! If you find our software useful for research, please cite the following papers in your own:

• “WebGraph: The Next Generation (Is in Rust)”, by Tommaso Fontana, Sebastiano Vigna, and Stefano Zacchiroli, in WWW '24: Companion Proceedings of the ACM on Web Conference 2024, pages 686-689. DOI 10.1145/3589335.3651581

• “The WebGraph Framework I: Compression Techniques”, by Paolo Boldi and Sebastiano Vigna, in _Proc. of the 13th international conference on World Wide Web, WWW 2004, pages 595-602, ACM. DOI 10.1145/988672.988752

Quick Setup

Assuming you have built all binaries, you will first need a graph in BV format, for example downloading it from the LAW website. For a graph with basename BASENAME, you will need the BASENAME.graph file (the bitstream containing a compressed representation of the graph), the BASENAME.properties file (metadata) and the BASENAME.offsets file (a bitstream containing pointers into the graph bitstream).

As a first step, if you need random access to the successors of a node, you need to build an Elias–Fano representation of the offsets (this part can be skipped if you just need sequential access). There is a CLI command webgraph with many subcommands, among which build, and webgraph build ef BASENAME will build the representation for you, serializing it with ε-serde in a file named BASENAME.ef.

Then, to load the graph you need to call

let graph = BVGraph::with_basename("BASENAME").load()?;

The with_basename method returns a LoadConfig instance that can be further customized, selecting endianness, type of memory access, and so on. By default you will get big endianness, memory mapping for both the graph and the offsets, and dynamic code dispatch.

Once you load the graph, you can retrieve the successors of a node or iterate on the whole graph. In particular, using the handy for_ macro, you can write an iteration on the graph as

for_!((src, succ) in graph {
    for dst in succ {
        [do something with the arc src -> dst]
    }
});

More Options

• By starting from the BVGraphSeq class you can obtain an instance that does not need the BASENAME.ef file, but provides only iteration.

• Graphs can be labeled by zipping them together with a labeling. In fact, graphs are just labelings with usize labels.

Operating on Graphs

There are many operations available on graphs, such as transpose and simplify. You can permute a graph.

Acknowledgments

This software has been partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU, and by project ANR COREGRAPHIE, grant ANR-20-CE23-0002 of the French Agence Nationale de la Recherche.

webgraph-rs's Issues

The BV graph compressor should save offsets

`webgraph build ef` failure on an old SWH graph

$ wget https://softwareheritage.s3.amazonaws.com/graph/2021-03-23-popular-3k-python/compressed/graph-labelled.labels
$ wget https://softwareheritage.s3.amazonaws.com/graph/2021-03-23-popular-3k-python/compressed/graph-labelled.labeloffsets
$ wget https://softwareheritage.s3.amazonaws.com/graph/2021-03-23-popular-3k-python/compressed/graph-labelled.properties


$ RUST_BACKTRACE=1 cargo run build ef /poolswh/softwareheritage/vlorentz/tmp/graph-labelled
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.30s
     Running `target/debug/webgraph build ef /poolswh/softwareheritage/vlorentz/tmp/graph-labelled`
thread 'main' panicked at src/cli/build/ef.rs:128:38:
called `Option::unwrap()` on a `None` value
stack backtrace:
   0: rust_begin_unwind
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panicking.rs:648:5
   1: core::panicking::panic_fmt
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/panicking.rs:72:14
   2: core::panicking::panic
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/panicking.rs:144:5
   3: core::option::unwrap_failed
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/option.rs:1983:5
   4: core::option::Option<T>::unwrap
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/option.rs:932:21
   5: webgraph::cli::build::ef::build_eliasfano
             at ./src/cli/build/ef.rs:128:21
   6: webgraph::cli::build::ef::main
             at ./src/cli/build/ef.rs:45:21
   7: webgraph::cli::build::main
             at ./src/cli/build/mod.rs:31:44
   8: webgraph::main
             at ./src/main.rs:70:5
   9: core::ops::function::FnOnce::call_once
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.


$ RUST_BACKTRACE=1 cargo run build ef /poolswh/softwareheritage/vlorentz/tmp/graph-labelled 45691500
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.08s
     Running `target/debug/webgraph build ef /poolswh/softwareheritage/vlorentz/tmp/graph-labelled 45691500`
[2024-03-21T09:47:53Z INFO  webgraph::cli::build::ef] The offsets file exists, reading it to build Elias-Fano
[2024-03-21T09:47:53Z INFO  dsi_progress_logger] Translating offsets to EliasFano...
Error: Could not write offset

Caused by:
    Value too large: 32618126984 >= 32618126984

Stack backtrace:
   0: anyhow::error::<impl anyhow::Error>::msg
             at /home/infres/ext-8972/.cargo/registry/src/index.crates.io-6f17d22bba15001f/anyhow-1.0.81/src/error.rs:83:36
   1: sux::dict::elias_fano::EliasFanoBuilder::push
             at /home/infres/ext-8972/.cargo/git/checkouts/sux-rs-2f90408a500ef4f7/933a962/src/dict/elias_fano.rs:88:13
   2: webgraph::cli::build::ef::build_eliasfano
             at ./src/cli/build/ef.rs:92:17
   3: webgraph::cli::build::ef::main
             at ./src/cli/build/ef.rs:45:21
   4: webgraph::cli::build::main
             at ./src/cli/build/mod.rs:31:44
   5: webgraph::main
             at ./src/main.rs:70:5
   6: core::ops::function::FnOnce::call_once
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/ops/function.rs:250:5
   7: std::sys_common::backtrace::__rust_begin_short_backtrace
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/sys_common/backtrace.rs:155:18
   8: std::rt::lang_start::{{closure}}
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/rt.rs:166:18
   9: core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/core/src/ops/function.rs:284:13
  10: std::panicking::try::do_call
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panicking.rs:555:40
  11: std::panicking::try
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panicking.rs:519:19
  12: std::panic::catch_unwind
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panic.rs:142:14
  13: std::rt::lang_start_internal::{{closure}}
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/rt.rs:148:48
  14: std::panicking::try::do_call
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panicking.rs:555:40
  15: std::panicking::try
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panicking.rs:519:19
  16: std::panic::catch_unwind
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/panic.rs:142:14
  17: std::rt::lang_start_internal
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/rt.rs:148:20
  18: std::rt::lang_start
             at /rustc/bb594538fc6e84213a6b8d5e165442570aa48923/library/std/src/rt.rs:165:17
  19: main
  20: __libc_start_main
             at ./csu/../csu/libc-start.c:308:16
  21: _start

This happens at least on both a somewhat old version we use in swh-graph (f460742) and the latest commit (3615f26)

Tracking issue for LLP porting

This is an issue that tracks problems and progress with the LLP porting.

• The current implementation does not perform the last combination step as it appears to be redundant. Redundancy has been tested on a few graphs but more testing would be good.
• The current implementation does not recombine with the best label after each other label. The reasons for this recombination in the code are not clear, and the effects appear to be negligible. However, this double the recombination time.
• We probably want to save the permutation with ε-serde. We do not want naked binary data around.
• Observing the result ɣ-by-ɣ, the Rust and Java implementations appear to have slightly different behavior for larger or smaller ɣ's: in one case Rust is better, in the other Java is better. It would be a good thing to understand why this happens, and if we can get better for all ɣ's.
• Granularity is presently at the node level. In Java it is at the arc level.

Implement exact-size iterators and lenders where possible

We need to go through the whole codebase and implement exact-size traits whenever possible.

code should be "cargo format" clean

... and currently isn't.

We should make sure the CI bails when the code isn't "cargo format" (currently it doesn't) and have a pre-commit hook that enforces this so that we minimize the changes of reintroducing divergence in the future.

(I'm postponing this for now because a lot of development is going on in the webgraph_reader branch. When merged into master it will be a good moment to format all the code and update the CI.)

Add checks for permutations

Currently, the CLI tools and PermutedGraph assume that the permutation is bijective but they never check it. We should add a check by default with the possibility to opt-out.

Implement a lending iterator

Size tables for writing

We need some benchmarking to find the better table size for the write tables.

LLP compression is 10% worse than the Java version

As per title.

This has been repeatedly verified on both the Software Heritage graph (by @progval) and on the cnr-2000 benchmark (by @vigna).

Reason unclear at the moment.

test utils::permuted_graph::test_sorted_permuted_graph fails with "Too many open files"

As per issue title. Here's a log from my computer:

$ cargo t sorted_permuted_graph
    Finished test [unoptimized + debuginfo] target(s) in 0.03s
     Running unittests src/lib.rs (target/debug/deps/webgraph-55ec38795ff86d05)

running 1 test
test utils::permuted_graph::test_sorted_permuted_graph ... FAILED

failures:

---- utils::permuted_graph::test_sorted_permuted_graph stdout ----
thread 'utils::permuted_graph::test_sorted_permuted_graph' panicked at 'called `Result::unwrap()` on an `Err` value:
  Os { code: 24, kind: Uncategorized, message: "Too many open files" }', src/utils/sort_pairs.rs:75:81
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Interestingly enough, the test does not fail on the CI (see example from a recent run).

We need sequential iterators starting from a given node

To leverage the speed of sequential decoding in parallel computations we need sequential iterators with a starting node.

Non-static ArcListGraph

Currently, ArcListGraph can only be created with 'static adjacency lists:

webgraph-rs/src/graph/arc_list_graph.rs

Lines 19 to 27 in 5cd97c3

	impl<I: IntoIterator<Item = (usize, usize)> + Clone + 'static> ArcListGraph<I> {
	/// Create a new graph from an iterator of pairs of nodes
	pub fn new(num_nodes: usize, iter: I) -> Self {
	Self {
	num_nodes,
	into_iter: iter,
	}
	}
	}

This means it can't be used with data loaded dynamically†, which is every non-toy use case (as far as i can tell)

What's your plan for this? I don't see a way out, my attempts to change it (either a lifetime parameter to ArcListGraph or Self: '_ bounds) make me end up in lifetime hell.

† There is a way out, though: load data into a Box, then leak it to get a 'static. Given that in practice I'll always end the process right after I'm done reading the ArcListGraph, this would be acceptable.

Implement simple iteration

Now we need to call iter_nodes(). It would be nice to have to do just for :.

Optimizations for parallel compression

The first compression thread could write to the final bitstream so we can avoid copying it.
This would require implementing seek for the buffered bitstream write, but this requires to read the current word and we often use BufWriter which does not implement Read.

Parallelize permutation inversion in LLP?

@zacchiro points out that the LLP process spends some non-negligeable time single-threaded

A quick look at perf top shows it is in this function:

webgraph-rs/src/algorithms/llp.rs

Line 194 in b4e4176

invert_in_place(&mut update_perm);

Would it make sense to allocate an array for another permutation, and invert the permutation not-in-place into that array so it can be parallelized?

It must be possible to load graphs into mapped memory

Transparent huge pages do not work in memory-mapped files, and they can bring a significant performance increase on very large graphs.

Thus, we need three ways to load a graph:

• mmap()'d file (with flags)
• heap-allocated memory
• mmap()-allocated memory (with flags)

This is identical to the possibilities we have in ε-serde with MemCase.

Encoder.flush should be Encoder.close, consume self, and return an associated type

Implement u8 load size with double read

To have u8 load size work transparently with decoding tables of at most 16 bits we need to load with size u8 twice. This will need some conditional compilations (all other loads happen once).

Transpose deadlocks

When too many files are opened, traspose deadlocks instead of panicking.

outdegree() method

We need an outdegree() method that returns the degree without expanding the compression data of a node.

In WebGraph, this is obtained by keeping a reader that is reused by the method. The result is that the structure is not thread safe and the whole LightweightPrototype mechanism. Thanks to the len() method for the successors() iterator I think we can turn page and keep the readers thread safe (and Send/Sync in Rust). The outdegree() method can clone a reader—it will be a bit heavy for the purpose, but outdegree() will be rarely used, if ever (and we can document this).

Node iterators with lifetimes

Sequential graphs would benefit from a weaker iterator specification:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9b64b71d0d22c09063e4e1419bf8dd76

In particular, this would make it possible to stop using the unsafe pointer dereference to batches of sorted pairs.

Maybe next_weak is not a good name. next_lt (lifetime)?

Tables and specialized methods for minimal binary codes of small size

Minimal binary codes of order 3 to 5 might benefit from a specialized implementation similar to read_zeta3. The case 3 and 5 might also benefit from very small tables (2 and 3 bits are sufficient) which would avoid the double-read-with-test current strategy. The case 4 is just equivalent to read 2 bits.

Tommaso made me notice that this is wrong. The length should decrease as the iterator progresses.

          Tommaso made me notice that this is wrong. The length should decrease as the iterator progresses.

Originally posted by @vigna in #32 (comment)

Missing LabelledGraphWrapper

We should have a wrapper that gives a Graph, and a wrapper that gives a generic map for node id -> labe implements a Labelled Graph

build.rs should generate code under OUT_DIR and non-generated Rust modules should include it

As discussed in more details in #12 (and independently from what happens with that PR, which does not fix this specific issue), build.rs should generate code under env::var_os("OUT_DIR") and corresponding real Rust modules should include!() the generated code.

References:

• https://doc.rust-lang.org/cargo/reference/build-scripts.html
• https://doc.rust-lang.org/cargo/reference/build-script-examples.html

(Unless/until this become completely moot because we settle on a "final" version of the generated codes and stop generating it every time.)

Implement ExactSizeIterator/ExactSizeLender whenever possible

cargo tarpaulin takes forever in the "Mapping coverage data to source" steps

$ time cargo tarpaulin --engine llvm &> ~/webgraph-cargo-tarpaulin.log
cargo tarpaulin --engine llvm &> ~/webgraph-cargo-tarpaulin.log  6972,49s user 64,53s system 106% cpu 1:50:12,05 total

Almost 2 hours, which is insane.
Looking at the log, it stands out how the "Mapping coverage data to source" of each test takes 6 minutes (on my laptop):

$ grep -A 1 Mapping webgraph-cargo-tarpaulin.log
Sep 17 17:09:09.499  INFO cargo_tarpaulin::statemachine::instrumented: Mapping coverage data to source
Sep 17 17:15:07.938  INFO cargo_tarpaulin::process_handling: running /srv/src/rust/webgraph-rs/webgraph-rs/target/debug/deps/test_read_webgraph-1d8b146a355a8791
--
Sep 17 17:15:08.153  INFO cargo_tarpaulin::statemachine::instrumented: Mapping coverage data to source
Sep 17 17:21:06.756  INFO cargo_tarpaulin::process_handling: running /srv/src/rust/webgraph-rs/webgraph-rs/target/debug/deps/test_bvcomp-fc6ba07461d5faa0
--
Sep 17 17:21:06.804  INFO cargo_tarpaulin::statemachine::instrumented: Mapping coverage data to source
Sep 17 17:27:06.529  INFO cargo_tarpaulin::process_handling: running /srv/src/rust/webgraph-rs/webgraph-rs/target/debug/deps/ascii_convert-8f34e854de046580

This looks like an upstream issue in tarpaulin, I'm going to report it there.

PS given it took two hours to obtain, the very least I can do is report here for posterity the current code coverage :-)

46.80% coverage, 1287/2750 lines covered

BatchIterator errors with "Cannot initialize mmap of size 0"

Somewhere between d3fec35 and 8a50f7e (or a dsi_bitstream update), BatchIterator broke:

---- algorithms::transpose::test_transposition_labeled stdout ----
Error: Could not mmap /tmp/.tmpkIBqin/000000

Caused by:
    0: Cannot initialize mmap of size 0
    1: invalid size

---- algorithms::transpose::test_transposition stdout ----
Error: Could not mmap /tmp/.tmpXafFAx/000000

Caused by:
    0: Cannot initialize mmap of size 0
    1: invalid size

---- utils::sort_pairs::test_push stdout ----
Error: Could not mmap /tmp/.tmpLt6kHU/000000

Caused by:
    0: Cannot initialize mmap of size 0
    1: invalid size

New format with different endianess for better performance

During today's review of the code we noticed that we read codes using a MSB to LSB order which implies the need to use big-endian words. Since most modern computers are little-endian we might want to add backends to support LSB to MSB order, thus little-endian order, which might result in better performance.

We will discuss this further in the future as it might lead only to marginal improvements and needs to be accurately benchmarked.

LLP: Failure to serialize labels causes a segfault

For some reason, when we early-return from this line (eg. because we ran out of disk in the temp dir):

webgraph-rs/src/algo/llp/mod.rs

Line 302 in 9cd0536

.context("Could not serialize labels")?;

then dropping the LabelStore segfaults.

For example, with this patch:

diff --git a/src/algo/llp/mod.rs b/src/algo/llp/mod.rs
index 2b5f514..6f14043 100644
--- a/src/algo/llp/mod.rs
+++ b/src/algo/llp/mod.rs
@@ -43,6 +43,7 @@ use rand::SeedableRng;
 use rayon::prelude::*;
 use std::collections::HashMap;
 use std::env::temp_dir;
+use std::mem::ManuallyDrop;
 use std::path::PathBuf;
 use std::sync::atomic::Ordering;
 use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize};
@@ -152,6 +153,7 @@ pub fn layered_label_propagation<R: RandomAccessGraph + Sync>(
             .iter()
             .for_each(|x| x.store(true, Ordering::Relaxed));
 
+        /*
         for update in 0.. {
             update_pl.start(format!("Starting update {}...", update));
 
@@ -270,6 +272,7 @@ pub fn layered_label_propagation<R: RandomAccessGraph + Sync>(
                 break;
             }
         }
+        */
 
         iter_pl.done();
 
@@ -295,11 +298,16 @@ pub fn layered_label_propagation<R: RandomAccessGraph + Sync>(
         costs.push(cost);
 
         // storing the perms
+        let path = labels_path(gamma_index);
+        info!("Creating {}", path.display());
         let mut file =
-            std::fs::File::create(labels_path(gamma_index)).context("Could not write labels")?;
-        labels
-            .serialize(&mut file)
-            .context("Could not serialize labels")?;
+            std::fs::File::create(&path).context("Could not write labels")?;
+        info!("Writing {}", path.display());
+        let res = labels
+            .serialize(&mut file);
+        info!("Res {:?}", res);
+        res.context("Could not serialize labels")?;
+        info!("Done writing {}", path.display());
 
         gamma_pl.update_and_display();
     }
diff --git a/src/cli/llp.rs b/src/cli/llp.rs
index 99c0151..d77a809 100644
--- a/src/cli/llp.rs
+++ b/src/cli/llp.rs
@@ -85,7 +85,7 @@ pub fn cli(command: Command) -> Command {
 pub fn main(submatches: &ArgMatches) -> Result<()> {
     let args = CliArgs::from_arg_matches(submatches)?;
 
-    match get_endianness(&args.basename)?.as_str() {
+    let main_res = match get_endianness(&args.basename)?.as_str() {
         #[cfg(any(
             feature = "be_bins",
             not(any(feature = "be_bins", feature = "le_bins"))
@@ -97,7 +97,10 @@ pub fn main(submatches: &ArgMatches) -> Result<()> {
         ))]
         LE::NAME => llp_impl::<LE>(args),
         e => panic!("Unknown endianness: {}", e),
-    }
+    };
+
+    log::info!("main res {:?}", main_res);
+    main_res
 }
 
 fn llp_impl<E: Endianness + 'static + Send + Sync>(args: CliArgs) -> Result<()>
@@ -157,7 +160,7 @@ where
     }
 
     // compute the LLP
-    let labels = llp::layered_label_propagation(
+    let res2 = llp::layered_label_propagation(
         &graph,
         &*deg_cumul,
         gammas,
@@ -166,8 +169,10 @@ where
         args.granularity,
         args.seed,
         predicate,
-    )
-    .context("Could not compute the LLP")?;
+    );
+    log::info!("res2 {:?}", res2);
+    let labels = res2.context("Could not compute the LLP")?;
+    log::info!("labels ok");
 
     let mut llp_perm = (0..graph.num_nodes()).collect::<Vec<_>>();
     llp_perm.par_sort_by(|&a, &b| labels[a].cmp(&labels[b]));

llp prints:

[2024-03-23T11:33:45Z INFO  webgraph::algo::llp] Log-gap cost: 68596432338
[2024-03-23T11:33:45Z INFO  webgraph::algo::llp] Creating /tmp/labels_0.bin
[2024-03-23T11:33:45Z INFO  webgraph::algo::llp] Writing /tmp/labels_0.bin
[2024-03-23T11:33:48Z INFO  webgraph::algo::llp] Res Err(WriteError)
Segmentation fault

and here is the traceback:

Thread 1 "webgraph" received signal SIGSEGV, Segmentation fault.                                                                        
__GI___libc_free (mem=0x7ffb32dfd010) at malloc.c:3102                                                                                  
3102    malloc.c: No such file or directory.                                                                                            
(gdb) bt                                                                                                                                
#0  __GI___libc_free (mem=0x7ffb32dfd010) at malloc.c:3102                                                                              
#1  0x00005555556459fa in alloc::alloc::dealloc (ptr=<optimized out>, layout=...) at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/alloc.rs:117                                                                                                              
#2  alloc::alloc::{impl#1}::deallocate (ptr=..., layout=..., self=<optimized out>) at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/alloc.rs:254                                                                                                             
#3  alloc::boxed::{impl#8}::drop<[core::sync::atomic::AtomicUsize], alloc::alloc::Global> (self=<optimized out>) at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/alloc/src/boxed.rs:1243                                                                              
#4  core::ptr::drop_in_place<alloc::boxed::Box<[core::sync::atomic::AtomicUsize], alloc::alloc::Global>> () at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs:507                                                                                   
#5  core::ptr::drop_in_place<webgraph::algo::llp::label_store::LabelStore> () at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs:507                                                                                                                 
#6  webgraph::algo::llp::layered_label_propagation<webgraph::graphs::bvgraph::random_access::BVGraph<webgraph::graphs::bvgraph::codecs::dec_dyn::DynCodesDecoderFactory<dsi_bitstream::traits::endianness::BigEndian, webgraph::graphs::bvgraph::codecs::factories::MemoryFactory
<dsi_bitstream::traits::endianness::BigEndian, webgraph::utils::mmap_helper::MmapHelper<u32, mmap_rs::mmap::Mmap>>, sux::dict::elias_fano::EliasFano<sux::rank_sel::select_fixed2::SelectFixed2<sux::bits::bit_vec::CountBitVec<&[usize]>, &[u64], 8, 2>, sux::bits::bit_field_ve
c::BitFieldVec<usize, &[usize]>>>>, sux::dict::elias_fano::EliasFano<sux::rank_sel::select_zero_fixed2::SelectZeroFixed2<sux::bits::bit_vec::CountBitVec<&[usize]>, &[u64], 8, 2>, sux::bits::bit_field_vec::BitFieldVec<usize, &[usize]>>, predicates::boxed::BoxPredicate<webgr
aph::algo::llp::preds::PredParams>> (sym_graph=<optimized out>, deg_cumul=<optimized out>, gammas=..., num_threads=..., chunk_size=..., granularity=..., seed=0, predicate=...) at src/algo/llp/mod.rs:357                                                                       
#7  0x00005555556c6b4d in webgraph::cli::llp::llp_impl<dsi_bitstream::traits::endianness::BigEndian> (args=...) at src/cli/llp.rs:163   
#8  webgraph::cli::llp::main (submatches=<optimized out>) at src/cli/llp.rs:93                                                          
#9  0x00005555555e222c in webgraph::main () at src/main.rs:70                                                                           
(gdb) f 4                                                                                                                               
#4  core::ptr::drop_in_place<alloc::boxed::Box<[core::sync::atomic::AtomicUsize], alloc::alloc::Global>> () at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs:507                                                                                   
507     /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs: No such file or directory.                         
(gdb) f                                                                                                                                 
#4  core::ptr::drop_in_place<alloc::boxed::Box<[core::sync::atomic::AtomicUsize], alloc::alloc::Global>> () at /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs:507                                                                                   
507     in /rustc/07dca489ac2d933c78d3c5158e3f43beefeb02ce/library/core/src/ptr/mod.rs                                                  

I assume this is due to the transmuted label_store.labels, but I don't see why the compiler would drop the transmuted before the original, let alone drop it at all. Wrapping in ManuallyDrop doesn't help.

This happens both in release and debug mode (I commented out the worker loop so it terminates within a reasonable time in debug mode)

Infinite loop in `BatchIterator::new_from_vec_sorted`

repro:

#[test]
fn test_batchiterator() -> Result<()> {
    let mut tempfile = temp_dir(std::env::temp_dir());
    tempfile.push_str("BatchIterator_buffer");
    BatchIterator::new_from_vec_sorted(&tempfile, &[(2, 16), (3, 19), (8, 1), (8, 6), (11, 15), (11, 20), (15, 16)])?.collect::<Vec<_>>();
    Ok(())
}

This is to be sensitive to the data; similar inputs with fewer or different tuples don't all trigger the bug.

I didn't have this issue with d3fec35

Using CompactArray for permutations

speaking of space used for permutations, I just noticed that we could probably halve it in the Software Heritage graph by using CompactArray instead of naive arrays, as we have 34 billion nodes (2^35).

Do you want me to try and see the impact on LLP performance?

AsMut<ThreadPool> as parameter does not support &ThreadPool

Implement iterator-splitting logic at the SequentialLabelling level

SequentialLabelling should have a method returning a splitting of iter() in k pieces with approximately equal degree sums. This could be implemented by scanning and cloning or more efficiently if offsets are available.

Parallel BVComp should not copy files when running with one thread

BitStream Buffer implementation discussion (u128 or not)

On a preliminary experiment (https://godbolt.org/z/nMeMEzszK) u128 is not optimized correctly by Rust / LLVM even when compiling with arguments -C opt-level=3 -C target-cpu=skylake.

Example

pub fn test(x: u128) -> u128 {
    x >> 3
}

is compiled to:

example::test:
        mov     rdx, rsi
        mov     rax, rdi
        shrd    rax, rsi, 3 ; Lat: 1 RTP: 0.5 Port 1*p1
        shr     rdx, 3      ; Lat: 3 RTP: 1.0 Port: 1*p06
        ret

While I'd expect the compiler to exploit the vpsrldq instruction like:

use std::arch::x86_64::{
    __m128i,
    _mm_srli_si128
};

pub unsafe fn test2(x: __m128i) -> __m128i {
    _mm_srli_si128(x, 3)
}

to obtain:

example::test2:
        mov     rax, rdi
        vmovdqa xmm0, xmmword ptr [rsi]
        vpsrldq xmm0, xmm0, 3 ; Lat: 1 RTP: 1.0 Port: 1*p5
        vmovdqa xmmword ptr [rdi], xmm0
        ret

The Latencies and the Reciprocal ThroughPut I signed in the Assembly are taken from https://uops.info for the Skylake architecture.

This fail of optimizing results in spending 3 cycles, since shr and shrd are independent and use different ports they are executed at the same time, instead of 1, resulting in a x3 slowdown of this operation.

This is not due to the compilation target since vpsrldq is an SSE2 instruction that skylake supports:

$ rustc --print cfg -C target-cpu=skylake
debug_assertions
panic="unwind"
target_abi=""
target_arch="x86_64"
target_endian="little"
target_env="gnu"
target_family="unix"
target_feature="adx"
target_feature="aes"
target_feature="avx"
target_feature="avx2"
target_feature="bmi1"
target_feature="bmi2"
target_feature="cmpxchg16b"
target_feature="ermsb"
target_feature="f16c"
target_feature="fma"
target_feature="fxsr"
target_feature="llvm14-builtins-abi"
target_feature="lzcnt"
target_feature="movbe"
target_feature="pclmulqdq"
target_feature="popcnt"
target_feature="rdrand"
target_feature="rdseed"
target_feature="sse"
target_feature="sse2" <--------------------
target_feature="sse3"
target_feature="sse4.1"
target_feature="sse4.2"
target_feature="ssse3"
target_feature="xsave"
target_feature="xsavec"
target_feature="xsaveopt"
target_feature="xsaves"
target_has_atomic="16"
target_has_atomic="32"
target_has_atomic="64"
target_has_atomic="8"
target_has_atomic="ptr"
target_has_atomic_equal_alignment="16"
target_has_atomic_equal_alignment="32"
target_has_atomic_equal_alignment="64"
target_has_atomic_equal_alignment="8"
target_has_atomic_equal_alignment="ptr"
target_has_atomic_load_store="16"
target_has_atomic_load_store="32"
target_has_atomic_load_store="64"
target_has_atomic_load_store="8"
target_has_atomic_load_store="ptr"
target_os="linux"
target_pointer_width="64"
target_thread_local
target_vendor="unknown"
unix

We should discuss how to proceed with the implementation.

cargo tarpaulin fails with weird argv error

$ cargo tarpaulin --engine=llvm
Sep 15 17:19:24.459  INFO cargo_tarpaulin::config: Creating config
Sep 15 17:19:24.555  INFO cargo_tarpaulin: Running Tarpaulin
Sep 15 17:19:24.555  INFO cargo_tarpaulin: Building project
Sep 15 17:19:24.555  INFO cargo_tarpaulin::cargo: Cleaning project
error: failed to run `rustc` to learn about target-specific information

Caused by:
  process didn't exit successfully: `/home/zack/.local/share/rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/rustc - --crate-name ___ --print=file-names -Cdebuginfo=2 --cfg=tarpaulin -Cinstrument-coverage -Clink-dead-code -Ctarget-cpu=native -A non-camel-case-types non-upper-case-globals non_snake_case --crate-type bin --crate-type rlib --crate-type dylib --crate-type cdylib --crate-type staticlib --crate-type proc-macro --print=sysroot --print=split-debuginfo --print=crate-name --print=cfg` (exit status: 1)
  --- stderr
  error: multiple input filenames provided (first two filenames are `-` and `non-upper-case-globals`)

Sep 15 17:19:24.635 ERROR cargo_tarpaulin: Cargo failed to run! Error: cargo run failed
Error: "Cargo failed to run! Error: cargo run failed"

Remove unsafe pointer dereference

@progval, if you have any suggestion on how to avoid this horrible pointer dereference we'd like to hear!

webgraph-rs/src/utils/coo_to_labelled_graph.rs

Line 113 in 95fe4ca

let node_iter = unsafe { &mut *self.node_iter_ptr };

The problem here is that the iterator of the successor on a node depends on the merged list of arcs. So we couldn't convince the borrow checker that it is safe to return it. It is possible that it is just that—unsafe, not because of limitations of the borrow checker or missing lifetimes, just because you cannot do this.

An alternative would be inversion of control, that is, either having a graph-writer trait or passing a lambda that given (node, succ) puts it in a writer. At that point all the logic connecting the merging process with the iterator would be in a function.

LLP does not remove temporary labels_XX.bin files when done

after running this:

time RUST_MIN_STACK=100000000 TMPDIR=`pwd`/tmp/ webgraph llp -g "-1,-2,-3,-4,-5,0-0" -j 72 /poolswh/softwareheritage/vlorentz/datasets/2023-09-06-recompressed/compressed/graph-bfs-simplified llp.perm &> llp.log

I noticed that temp files have not been cleaned from the local temp dir:

$ du -sh tmp 
1,5T    tmp
$ ls -l tmp 
total 1600507005
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 11 17:27 labels_0.bin
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 11 20:29 labels_1.bin
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 11 23:24 labels_2.bin
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 12 02:52 labels_3.bin
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 12 06:59 labels_4.bin
-rw-rw-r--+ 1 szacchiroli tss 272972530072 apr 12 15:15 labels_5.bin

@progval have you ever encountered this? I'm surprised we didn't notice before… (maybe because you independently cleanup the same dir in the swh-graph pipeline?)