That sounds like an interesting approach. I’m not sure I get the mixing of hash map and skip list. I know HashMap already treeifies buckets that get too big to keep an O(log(N)) worst case for Comparable keys. But maybe you meant something else or we are talking about an alternative hash table implementation?
Anyway I’d be very curious to try this out. :-) I’ll see if I can make the high in-degree constraint a me problem so you only need to reason about cycles, if that helps with the skip lists. Thanks, /Erik On 27 Jul 2026, at 22:19, Benedict Elliott Smith <[email protected]> wrote: Yes, C-7282 uses a singly-linked list. If the map were adopted we might ideally improve it in future so that it had a skip-list fallback for regions of the list where the hash distribution is poor. That is, if the distance between two hash indexes Yes, C-7282 uses a singly-linked list. If the map were adopted we might ideally improve it in future so that it had a skip-list fallback for regions of the list where the hash distribution is poor. That is, if the distance between two hash indexes is greater than N nodes, we would prefer to degrade to O(log(N)). While the hash distribution is good you obviously prefer to have singly-linked list. But, even if this improvement were to materialise, you would expect almost all collections to have ~1 level since we use a high quality hash function. On 2026/07/27 13:13:34 Erik Osterlund via dev wrote: > Hi Benedict, > > Thank you for offering. It would be very helpful to try it out indeed, if it > isn’t too much hassle to set it up. > Would the ordered list be singly linked? I’m hoping so because of cycles. > > The Trie memtables did indeed work out very well, after a minor tweak. > > Thanks, > /Erik > > On 27 Jul 2026, at 12:22, Benedict Elliott Smith <[email protected]> wrote: > > This Message Is From an External Sender > This message came from outside your organization. > <https://us-phishalarm-ewt.proofpoint.com/EWT/v1/ACWV5N9M2RV99hQ!Op2yXeLH-cgOf_AgNzK--MM6SvdmzeSBbLXoROvTgptQGdDGwfUKdAktnYG2qvQcq9L6KUaPETz4eMU375Ut0VhHiRpeOW-8nS06Y6Q3S4GIbXx1TqPm0LnZcV_awH8$ > > > Report Suspicious > > CASSANDRA-7282 is pretty much a complete implementation, and should be easily > rebased. I wouldn't mind doing it if it helped test out such an interesting > GC improvement, it is anyway a shame it has languished for so long. > > Trie memtables seem like they're already well placed for this experiment. > > On 2026/07/27 10:09:00 Dmitry Konstantinov wrote: > > Hi Erik, > > Thanks for the email! We're always happy to welcome JVM developers here. > > We also have Trie memtable implementation for memtable <partition key ---> > > partition data> map - [1],[2],[5] > > It can keep some portion of data off-heap also but the underlying objects > > are still in heap: > > > > [image: image.png] > > > > There is an idea about extending Trie implementation and moving more parts > > of it to off-heap - [3]. > > There is also another idea for the map but it has not been implemented so > > far: [4] > > > > [1] > > https://urldefense.com/v3/__https://cassandra.apache.org/_/blog/Apache-Cassandra-5.0-Features-Trie-Memtables-and-Trie-Indexed-SSTables.html__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-9xcjyrA$ >> > > [2] > > https://urldefense.com/v3/__https://www.vldb.org/pvldb/vol15/p3359-lambov.pdf__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW8x7ctJIw$ >> [3] > > https://urldefense.com/v3/__https://cwiki.apache.org/confluence/spaces/CASSANDRA/pages/392038876/CEP-57*Flat*keys*and*trie*interfaces__;KysrKys!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-71YRlTg$ >> > > [4] > > https://urldefense.com/v3/__https://issues.apache.org/jira/browse/CASSANDRA-7282__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW-07j5veQ$ >> [5] > > https://urldefense.com/v3/__https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/db/memtable/TrieMemtable.java__;!!ACWV5N9M2RV99hQ!LLmu0KkRwNv67hDnb6rzmQXgkzkf_KFT3xiBv4qLkVEK27NS5t2ypfRUQzcEcqyVbcfAX46YNyAEkW_72alOLg$ >> > > Regards, > > Dmitry > > > > On Mon, 27 Jul 2026 at 10:45, Erik Osterlund via dev < > > [email protected]<mailto:[email protected]>> wrote: > > > > > Hi, > > > > > > I’m one of the ZGC devs. Have been playing around a bit with an > > > interesting algorithmic extension of generational ZGC using a form of > > > reference counting in the old generation. This allows us to essentially > > > have young generation collections reclaim zero reference count old > > > objects, > > > and free up acyclic garbage in the old generation as well, just before it > > > promotes objects from the young generation to the old generation. The > > > consequence is that as long as long-lived garbage is acyclic, we pretty > > > much don’t need to do major collections other than to defragment memory > > > every now and then. But the actual pressure to reclaim old garbage > > > vanishes > > > and is handled from the young collections. > > > > > > One quirk is that in this scheme, we can reclaim objects that never have > > > an in-degree higher than 6, because then accounting isn’t free any longer > > > (we are using available object header bits). > > > > > > I was delighted to find that cassandra memtables using skip lists are > > > acyclic. But unfortunately I think the base nodes of the skip lists get > > > too > > > high in-degree and ultimately end up spoiling eager reclamation. > > > > > > So I’m wondering, how annoying would it be to change this map > > > implementation to something that is both acyclic and has ref counts lower > > > than 7 for any internal nodes? If that’s not too tricky to do, I suspect > > > we > > > could collapse the GC overheads related to having memtables in-heap. Maybe > > > a tree structure or something? What do you guys think? If it’s too > > > annoying > > > that’s good feedback too. > > > > > > Please let me know if this is the wrong place for this kind of discussion. > > > > > > Thanks, > > > /Erik > > > > > > > > -- > > Dmitry Konstantinov > > > > >
