-
Notifications
You must be signed in to change notification settings - Fork 94
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Interest in a single value map? #45
Comments
Glad to hear it! Out of curiosity, how much of a difference did the swap from As far as merging goes, I'd prefer finding a way to avoid replicating much of the unsafety. One way to do so might be to provide a thin wrapper type around evmap that has an API that assumes and enforces just one entry per key. And behind the scenes that would always benefit from the one-slot space held by the |
I clone them. I couldn't figure out a way without each update cloning the value, modifying the clone, deleting the old entry and finally inserting the update. The savings is mostly in the update code that is simpler and lets me clone only once at creation. I was thinking of two solutions to multiple largely redundant unsafe blocks. One is to have a back end with all the unsafe that both maps use. This is probably too hard to get right, but if we did it would be nice.
The mono map would then just be a I hadn't thought of having a the monomap be a single-value enforced multimap. I don't think it'd work with a single value in the |
A back end that holds the data and that both maps update would not be safe, since you'd then still have read-write conflicts on it. You could of course always use a lock, but that's equivalent to having your data type be Having both a cloned and a non-cloned value seems like a very strange design indeed. Are there use-cases where someone would need both? I'm hesitant to have to juggle two different types of values in an already complex data-structure — it makes it much more likely that there'll be bugs. Ah, yes, I was proposing just using the Ultimately, I don't think extending evmap to supporting |
My KNN data structure is a tree where the nodes have several fields that hold cached results and other information, and a list of children. Since the list of children is small, between 1 and 20 ints, I just clone it. The clustering is similar, but with a much bigger child list and a much more complicated metadata to enable some topological data analysis. I think this use case might be specialized for trees, so if you don't want the added complexity I could fork it and call it |
I wonder -- have you benchmarked just replacing the child list instead of updating it in-place? My guess is that it won't be that much slower. |
I have not, I ran into issue updating the metadata early and then made the monomap. The child list isn't updated often, so I don't think it'll change the overall performance much. |
Might be worth trying that so that you don't have to maintain your own fork :) We could in theory also provide a handy method for "replace by calling a closure", which sounds like it might work well in your case! |
That could greatly simplify the code for most. I can make a PR for that. I forked my mono-map a while ago. There's been a lot of changes since then :D. |
Hehe, I believe it. Many of them should make the map much nicer to work with! From memory, some of them were also correctness fixes. |
Here's the lib I used the fork in: https://github.com/comath/grandma The fork is currently a vestigial library embedded in the code. I haven't had a chance to try the changes you suggested. If they work I'll add them and not fork, but if not I can just fork. Grandma is currently 3rd near complete rewrite of this library and doesn't yet have a some of the old features that the previous generations had. The first generation used traditional references to build the tree, with RwLocks where needed, and the second used a arena with a hashmap with per bucket locking. The node-cache updates in the old generations absolutely killed the performance. Just querying the tree with this evmap fork is much faster, I haven't tried cache updates yet. |
FWIW I would also be interested in this, and also a unique-key (like a normal hashmap instead of a bag) version. |
I spent some more time thinking about this in the context of #70, and I wonder if the real solution here is to abstract away the core concurrency primitive from I think what you'd want is a
trait Absorb<O> {
fn apply_first(&mut self, op: &mut O);
fn apply_second(&mut self, op: O);
} This, I think, should let today's LeftRight<HashMap<K, Values<V>>, Operation<K, V>> with an appropriate LeftRight<HashMap<K, V>, SingleOperation<K, V>>
impl WriteHandle<O> {
fn refresh(&mut self);
fn append_op(&mut self, op: O);
} Now, I think implementing all of this would be super neat, and I think it would enable a number of neat use cases like super fast vectors, |
This patch set sxtract the core concurrency primitive from evmap by implementing the plan from #45 (comment). It fixes #45 and #70 by allowing separate implementations of the data structure that re-use the concurrency primitive. Fixes #67 by making `ReadGuard::map` public.
Thanks for this great lib! This cleared up a significant bottleneck for me.
I have an eventually consistent editable KNN data structure that I'm using a simplification/modification of this library for. I changed the value of the hashmaps from a
SmallVec<T>
to just aT
and changed the operations to justinsert
,update
andremove
. My objects are relatively small, but complex. Doing small updates in place is more critical than the memory savings. You can find the modification here: https://github.com/comath/rust-evmap/tree/master/src/monomapIs there any interest in a PR to bring this modification into this lib? There's a similar issue here.
The text was updated successfully, but these errors were encountered: