Date: Tue, 9 Feb 2021 18:10:38 -0700
> 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.
>> *shrug*
>
> 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:
unordered_list
unordered_block_list
unordered_bucket_array_list
unordered_sparse_list
unordered_change_list
unordered_sparse_collection
sparse_agglomeration
sparse_aggregate
sparse_list
sparse_block_list
or
bucket_list ;)
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.
Jeff
>
> 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.
>> *shrug*
>
> 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:
unordered_list
unordered_block_list
unordered_bucket_array_list
unordered_sparse_list
unordered_change_list
unordered_sparse_collection
sparse_agglomeration
sparse_aggregate
sparse_list
sparse_block_list
or
bucket_list ;)
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.
Jeff
Received on 2021-02-09 19:10:45