Currently the mosts cpu consumming parts of MeiliDB are the criterions, it is almost 40% of the total time (for 9 million fields).
We spotted something interresting in time measurements, one of our criterion takes much more time than the others but it only does a sum of one of the Match property.
The sum_of_typos criterion takes 5.41ms to sort 97360 documents and the sum_of_words_attribute takes 19.76ms for the exact same number of documents.
97360 total documents to classify
626460 total matches to classify
query_all took 87.45 ms
criterion SumOfTypos, documents group of size 97360
criterion SumOfTypos sort took 5.41 ms
criterion NumberOfWords, documents group of size 97360
criterion NumberOfWords sort took 5.36 ms
criterion WordsProximity, documents group of size 97360
criterion WordsProximity sort took 7.24 ms
criterion SumOfWordsAttribute, documents group of size 97360
criterion SumOfWordsAttribute sort took 19.76 ms
criterion SumOfWordsPosition, documents group of size 33657
criterion SumOfWordsPosition sort took 10.48 ms
criterion Exact, documents group of size 16708
criterion Exact sort took 1.96 ms
criterion DocumentId, documents group of size 16708
criterion DocumentId sort took 1.98 ms
It is nearly the sames algorithms:
https://github.com/Kerollmops/MeiliDB/blob/0a3d069fbc0108cca6953c813453b2dd24d8b68d/src/rank/criterion/sum_of_typos.rs#L14-L26
https://github.com/Kerollmops/MeiliDB/blob/0a3d069fbc0108cca6953c813453b2dd24d8b68d/src/rank/criterion/sum_of_words_attribute.rs#L13-L19
The only difference is that the attribute field is not at the start of Match.
It is probably padded, making the CPU cache unhappy.
struct Match {
query_index: u32,
distance: u8,
attribute: u16,
word_index: u32,
is_exact: bool,
}So we thought about data oriented design, putting related data in the same memory space to make the CPU cache happy.
All of these fields will probably be stored in the same vectors, each vector represent a property.
All of the documents matches properties will be in the same five vectors, everything is a matter of indexes and slices.
// OLD algorithm struct
struct Match {
query_index: u32,
distance: u8,
attribute: u16,
word_index: u32,
is_exact: bool,
}
let matches: Vec<Match>;
// NEW algorithm struct
struct Matches {
query_index: Vec<u32>,
distance: Vec<u8>,
attribute: Vec<u16>,
word_index: Vec<u32>,
is_exact: Vec<bool>,
}https://stackoverflow.com/questions/17074324/how-can-i-sort-two-vectors-in-the-same-way-with-criteria-that-uses-only-one-of
Currently the mosts cpu consumming parts of MeiliDB are the criterions, it is almost 40% of the total time (for 9 million fields).
We spotted something interresting in time measurements, one of our criterion takes much more time than the others but it only does a sum of one of the
Matchproperty.The
sum_of_typoscriterion takes 5.41ms to sort 97360 documents and thesum_of_words_attributetakes 19.76ms for the exact same number of documents.It is nearly the sames algorithms:
https://github.com/Kerollmops/MeiliDB/blob/0a3d069fbc0108cca6953c813453b2dd24d8b68d/src/rank/criterion/sum_of_typos.rs#L14-L26
https://github.com/Kerollmops/MeiliDB/blob/0a3d069fbc0108cca6953c813453b2dd24d8b68d/src/rank/criterion/sum_of_words_attribute.rs#L13-L19
The only difference is that the
attributefield is not at the start ofMatch.It is probably padded, making the CPU cache unhappy.
So we thought about data oriented design, putting related data in the same memory space to make the CPU cache happy.
All of these fields will probably be stored in the same vectors, each vector represent a property.
All of the documents matches properties will be in the same five vectors, everything is a matter of indexes and slices.
https://stackoverflow.com/questions/17074324/how-can-i-sort-two-vectors-in-the-same-way-with-criteria-that-uses-only-one-of