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 > > > > >
