[MOD-8973] Rust trie iterators by hdoordt · Pull Request #5928 · RediSearch/RediSearch

hdoordt · 2025-04-14T15:20:59Z

To do:

Describe the changes in the pull request

A clear and concise description of what the PR is solving, including:

Current: The current state briefly
Change: What is the change
Outcome: Adding the outcome

Which additional issues this PR fixes

MOD-...
#...

Main objects this PR modified

...

Mark if applicable

This PR introduces API changes
This PR introduces serialization changes

src/redisearch_rs/redis_module_test/build.rs

LukeMathWalker · 2025-04-15T09:14:36Z

src/redisearch_rs/trie_bencher/src/bencher.rs

+    let map = Rc::new(map);
+    group.bench_function("Rust", |b| {
+        b.iter_batched(
+            || map.clone(),
+            |map| {
+                map.lending_iter_prefix(&pattern).for_each(|entry| {
+                    black_box(entry);
+                });
+            },
+            BatchSize::LargeInput,
+        );
+    });


Suggested change

let map = Rc::new(map);

group.bench_function("Rust", |b| {

b.iter_batched(

|| map.clone(),

|map| {

map.lending_iter_prefix(&pattern).for_each(|entry| {

black_box(entry);

});

},

BatchSize::LargeInput,

);

});

group.bench_function("Rust", |b| {

b.iter(|| {

map.lending_iter_prefix(&pattern).for_each(|entry| {

black_box(entry);

})

})

});

We can use iter directly ^ whenever the benchmark is immutable, thus avoiding the Rc workaround.

LukeMathWalker · 2025-04-15T09:17:44Z

src/redisearch_rs/trie_bencher/src/bencher.rs

+        b.iter_batched(
+            || map.clone(),
+            |map| {
+                let pat: &[u8] = unsafe { std::mem::transmute(&*pattern) };


Wouldn't as_bytes do the trick here?

src/redisearch_rs/trie_rs/Cargo.toml

github-actions · 2025-04-15T15:56:16Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T09:45:30Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T15:51:57Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T16:06:16Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T17:35:30Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T17:52:10Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T17:58:14Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T17:59:38Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T18:05:04Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-16T18:24:28Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-17T12:59:04Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-17T13:13:37Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

Moves the bindings to `redismodule.h` in the newly created `redis_modules_test`, along with the Redis allocator shims and a number of utilities. This allows for reusing them in tests outside of `trie_bencher`.

`TrieMap_Iterate` is implemented by applying different iterator adaptors to `trie_rs::iter::LendingIter`, based on the passed iteration mode. `TrieMapIterator_Next` simply obtains the next value from the iterator, and `TrieMapIterator_NextContains` and `TrieMapIterator_NextWildcard` deletage to `TrieMapIterator_Next`. This commit furthermore adds a number of tests to validate the correct operation of the triemap iterator functionality exposed in the `trie_rs::ffi` module. This commit also removes the global allocator definition set in `trie_rs`, as it hinders tests and is to be moved to a façade crate.

Add support for backtracking in `wildcard::TokenStream::matches`, based on the iterate algorithm described by [Dogan Kurt] [Dogan Kurt]: http://dodobyte.com/wildcard.html

Add proptests for the `wildcard::TokenStream::matches` method. One generates random patterns and keys, and validates that the keys match the patterns if and only if the [reference crate]'s implementation matches. The second one constructs keys that match the pattern and validates that they match. [reference crate]: https://github.com/cloudflare/wildcard/

Implement TriMap_IterateRange, and add a test

Implement TrieMap_RandomValueByPrefix and add a test

github-actions · 2025-04-22T14:56:43Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-22T15:37:48Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-22T15:42:48Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-22T15:42:58Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-22T15:48:23Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

github-actions · 2025-04-22T15:56:09Z

This PR exceeds the recommended size of 1000 lines. Please make sure you are NOT addressing multiple issues with one PR. Note this PR might be rejected due to its size.

hdoordt marked this pull request as draft April 14, 2025 15:21

hdoordt force-pushed the rust-trie-iter branch from adb0505 to c5109dd Compare April 14, 2025 15:28

github-actions bot added the size:XL label Apr 14, 2025

RediSearch deleted a comment from github-actions bot Apr 14, 2025

LukeMathWalker reviewed Apr 15, 2025

View reviewed changes

src/redisearch_rs/redis_module_test/build.rs Show resolved Hide resolved

LukeMathWalker reviewed Apr 15, 2025

View reviewed changes

src/redisearch_rs/trie_rs/Cargo.toml Outdated Show resolved Hide resolved

hdoordt force-pushed the rust-trie-iter branch from c5109dd to ffcfafe Compare April 15, 2025 15:55

hdoordt force-pushed the rust-trie-iter branch from ffcfafe to c719e7b Compare April 16, 2025 09:45

hdoordt force-pushed the rust-trie-iter branch from c719e7b to 926e1e5 Compare April 16, 2025 15:51

hdoordt force-pushed the rust-trie-iter branch from 926e1e5 to 7532269 Compare April 16, 2025 16:05

hdoordt force-pushed the rust-trie-iter branch from 7532269 to 0c50da5 Compare April 16, 2025 17:35

hdoordt force-pushed the rust-trie-iter branch from 0c50da5 to 84eb0bc Compare April 16, 2025 17:51

hdoordt force-pushed the rust-trie-iter branch from 84eb0bc to eec7bdc Compare April 16, 2025 17:57

hdoordt force-pushed the rust-trie-iter branch from c4323c6 to 96ef66c Compare April 16, 2025 18:04

hdoordt force-pushed the rust-trie-iter branch from 96ef66c to 86742fd Compare April 16, 2025 18:24

hdoordt force-pushed the rust-trie-iter branch from 86742fd to 9d1c667 Compare April 17, 2025 12:58

hdoordt added 8 commits April 22, 2025 16:55

Create redis_module_test crate for testing utilities

cc47b48

Moves the bindings to `redismodule.h` in the newly created `redis_modules_test`, along with the Redis allocator shims and a number of utilities. This allows for reusing them in tests outside of `trie_bencher`.

Implement trie_rs::ffi::TrieMapIterator_SetTimeout

a830c1f

Implement trie_rs::ffi::TrieMap_IterateRange

718bc2e

Implement TriMap_IterateRange, and add a test

Implement trie_rs::ffi::TrieMap_RandomValueByPrefix

bfd9c88

Implement TrieMap_RandomValueByPrefix and add a test

WIP on trie iterator benchmarks

f53d155

LukeMathWalker force-pushed the rust-trie-iter branch from 7e44c3a to f53d155 Compare April 22, 2025 14:55

LukeMathWalker force-pushed the rust-trie-iter branch from fc175ea to 0231743 Compare April 22, 2025 15:42

Comments

5fe979f

LukeMathWalker force-pushed the rust-trie-iter branch from 0231743 to 5fe979f Compare April 22, 2025 15:42

Remove duplicate test cases

e10ad09

Clarify the documentation for parse

b4edfdd

LukeMathWalker added 5 commits April 23, 2025 11:23

Remove the need for coercion by making Token less general

514dcce

Move tests to the integration folder

db63611

Comments

d8ad023

Support partial matches

7a73944

Rename TokenStream to WildcardPattern

89cd827

LukeMathWalker force-pushed the rust-trie-iter branch from 55e0c91 to 89cd827 Compare April 23, 2025 14:24

LukeMathWalker mentioned this pull request Apr 23, 2025

[MOD-9547] Implement wildcard matching, as a preliminary step towards wildcard trie iterators. #6000

Merged

2 tasks

Optimize traversals by skipping entire sub-trees if possible

d380504

LukeMathWalker mentioned this pull request Apr 24, 2025

[MOD-9547] Core trie iterators #6016

Merged

2 tasks

LukeMathWalker closed this Jun 13, 2025

Conversation

hdoordt commented Apr 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

To do:

Describe the changes in the pull request

Which additional issues this PR fixes

Main objects this PR modified

Mark if applicable

Uh oh!

Uh oh!

LukeMathWalker Apr 15, 2025

Choose a reason for hiding this comment

Uh oh!

LukeMathWalker Apr 15, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

github-actions bot commented Apr 15, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 16, 2025

Uh oh!

github-actions bot commented Apr 17, 2025

Uh oh!

github-actions bot commented Apr 17, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

github-actions bot commented Apr 22, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

hdoordt commented Apr 14, 2025 •

edited

Loading