daac-tools / daachorse Goto Github PK

I found that in practice, use of DoubleArrayAhoCorasick::<V>::deserialize_unchecked() can be extremely slow. It typically takes 4-5s on my m1 (16gb ram) machine.

Here are some stats:

heap_bytes=90855648 // .heap_bytes()
num_states=7440593  // .num_states()

2023-12-11T01:35:52.049237Z  INFO load_index{index_file="index.bin"}:load:deserialize
2023-12-11T01:35:56.495537Z  INFO ...

as title

Context: https://twitter.com/geofflangdale/status/1628585585198907393?s=20

Hi:
I wonder if this library support serialization of an automaton to disk? And if so, does it support memory mapping such file?

Daachorse handles a value-length pair as a pattern's output (see https://github.com/daac-tools/daachorse/blob/main/src/lib.rs#L289-L292)

In the current implementation, 31 bits and 32 bits are assigned to length and value, respectively. (1 bit is used for the flag,)
But, in many cases, the assignment is too rich.
For example, when the maximum length is 255, 1 byte is sufficient to represent.

If we know the maximum length and value, we can memory-efficiently store members on byte-aligned memory.
For example, if a length is represented in 1 byte and a value (with flag) is represented in 3 bytes, we can interleave them in a byte array outputs as follows.

outputs[0] = length 1
outputs[1] = value 1
outputs[2] = value 1
outputs[3] = value 1
outputs[4] = length 2
outputs[5] = value 2
outputs[6] = value 2
outputs[7] = value 2
...