Subject: Re: [isocpp-lib-ext] std::colony name brainstorming
From: Jeff Garland (jeff_at_[hidden])
Date: 2021-02-09 19:10:38
> On Feb 9, 2021, at 2:25 PM, Ville Voutilainen via Lib-Ext <lib-ext_at_[hidden]> wrote:
> On Tue, 9 Feb 2021 at 23:11, Matt Bentley via Lib-Ext
> <lib-ext_at_[hidden]> wrote:
>> Colony: an analogy using the idea of houses as memory blocks, rooms as
>> empty element memory spaces where elements come-and-go from. Ant colony
>> works just as well with tunnels, rooms and ants.
> I was about to suggest adding this excellent explanation to the paper,
> but it's already in it in
> Appendix D, now that I re-read the paper knowing what to look for.
> I think we're done here, naming-wise.
Well, letâs see about that. Iâve been quietly reading this chain because my first reaction to the name of this collection was basically âwutâ (it wasnât that nice actually, but keeping it PG). The house and room analogy is a stretch for me. Houses and rooms build up to neighborhoods â houses and neighborhoods arenât very dynamic â this collection is built for change. And then thereâs the whole âhistory of colonizationâ meta topic wrt the name.
So letâs do some other analysis. If we put âcolonyâ into google, weâre not going to find plf::colony at all â in fact weâre not going to find any results related to computer science in any way. Put in âcolony computingâ or âcolony data structure' â interestingly, and I think unfortunately for this name, âant colony optimizationâ comes up (new to me today). This data structure is unrelated to these optimization algorithms â since they are graph traversal algorithms. My conclusion is that the name is completely novel, possibly misleading, and not obvious to the target audience (computer scientists).
Now weâre left looking for terminology that might more directly describe the characteristics of this data structure. Right up front in the paper the words âbucket arrayâ are used to describe help describe the facility. It also uses a skip fields, not to be confused with a skip list. bucket and bucket array could get confusing bc of itâs use in hash tables. bucket_list might just be that killer name (1/2 smirk).
We have other properties such as unordered, composed of a list of memory blocks chained together. At this point, it occurred to me that âblock chainâ was the killer name â but alas, that might be spoken for ;) The primary benefit of the structure seems to be that itâs super good at handling changes well â rapid and frequent adds and removals - while keeping stable iterators. Interestingly, the underlying storage after lots of adds and removes interestingly becomes âsparselyâ populated groups of âblocks'.
Most my suggestions use âlistâ. Why? Because I think from a usage point of view it models properties weâd think of in list the most -- with the exception of maintaining insert order. So hereâs a few suggestions:
Iâve been aware of this paper for awhile, but Iâve now read it much more carefully. And watched the 2016 cppcon talk, which is quite helpful in understanding the context â it might be worth referencing the talk in the paper. Thank you Matt for bringing this novel bit of work to us.
SG14 list run by firstname.lastname@example.org
Older Archives on Google Groups