Efficient BTreeMap pruning

help
1

Hello there,

I'm creating a memory based session library that I hope to publish in crates.io soon. I wanted to enable a function in the SessionManager so that it could delete expired sessions once in a while (once a day/hour or so). But I want to do it as efficient as possible. I managed to get this, which is not working:

And I know I could do a filter_map() and clone each element returning Some(element), but I would like to avoid cloning as far as possible. Is that possible?

2

Well, you could just copy out all the IDs of the expired sessions and then delete them but that might be a bit slow (n*O(log(n))). You could do the same thing with a hash-map in O(n) time but then you pay the price for hashing twice.

Also, this doesn't answer your specific question, but I've written a library for exactly this use-case called stash. Basically, it's an very fast O(1) insert/delete/lookup table for cases where you don't care about the keys (it will pick them for you). In this case, I assume that you never want to reuse session IDs so you'd need to use UniqueStash. Unfortunately,

  1. You're keys will be larger (128bits on a 64bit machine).
  2. Iteration is O(capacity) even if you've deleted lots of items. This is fine as long as you don't have usage spikes. I can probably optimize this but I don't really have the time ATM.
  3. It doesn't yet have any form of retain method (what you're looking for). However, you can implement this as described above. (I can also add it when I have some free time).

Benchmarks: *scratch*.txt ยท GitHub

If you find it useful, I'll put it on crates.io (I just don't want to needlessly pollute the crates.io namespace).

3

Seems useful to me! I will use it :slight_smile:

Oh, btw, it would be useful to be able to convert tags to unique strings.

4

Oh, btw, it would be useful to be able to convert tags to unique strings.

I've uploaded a version to cargo where Tag implements FromStr. You should now be able to write let id: Tag = my_string.parse()?;.

5

I'm actually using stable, so I guess it would be with try!, wouldn't it?

Are strings always the same length? I would like to construct some sort of encrypted session value to send to the user, but I guess I can simply encrypt the actual tag.

Oh, and are the tags unique even when restarting? I guess I would need some sort of persistent storage in that case, right?

6

It doesn't currently provide any way of persisting the data and the tags are only unique within a single UniqueStash so no (although I could probably add support sometime in September).

If you don't care about persisting the sessions but still want globally unique IDs, you can just just make session IDs "GLOBAL_ID/TAG" (where you pick a new GLOBAL_ID whenever you start your program) and check GLOBAL_ID yourself.

7

I figured out I would need something like that. Thanks for the support!!