Date: Wed, 10 Feb 2021 07:45:46 -0700
> On Feb 10, 2021, at 6:53 AM, Ville Voutilainen <ville.voutilainen_at_[hidden]> wrote:
>
> On Wed, 10 Feb 2021 at 15:37, Jeff Garland
> <jeff_at_[hidden]> wrote:
>> I don't understand what the term sparse is supposed to tell me about a
>> list. If a list isn't sparse, it's broken.
>> I don’t think of lists as ’sparse’ — they typically have no extra storage. Nodes are allocated and removed as needed. This ‘list’ is special in that it doesn’t immediately deallocate storage when removing an element. It’s a ‘list of allocated slots’. Then it pulls a nifty accounting trick to allow O(N) traversal - a classic time/space trade.
>
> Right. But sparse vs. dense matrices are what I think about when I see
> a suggestion for a sparse list,
> and I don't see how this std::hive (yay, surreptitious sleight-of-hand
> in play, caveat emptor :P) is more
> sparse than a linked list, it seems *less* sparse because there are
> allocated-but-skipped slots in it.
Ok — if I follow you’re saying a ’sparse matrix’ representation would have less storage per unit size than a ‘dense matrix’. Interesting.
>
>> Colony also doesn't behave like a list performance-wise, considering
>> all of its operations, so I don't know
>> why we'd suggest that it's a list.
>> unordered_map doesn’t perform like map either. And as far as I can tell it’s performance properties are unlike any existing container.
>
> Heh, yeah. When pondering about this, I came to a similar conclusion
> that unordered_map and unordered_set aren't
> very descriptive names in some regards.
If there’s a common theme in naming discussions it’s that we can’t get ‘all properties’ in the name. w.r.t. performance, that’s such a complex issue that it seems unlikely we can use it well in naming. std::list ‘in theory’ has certain performance properties based on the number of operations — only problem is modern machines don’t work like old machines -- and so the model is now obsolete, with vector obliterating list in cases where theory would suggest otherwise. My point is that the performance isn’t static over time bc it depends on ever changing machine architectures. So in the case of the names I think unordered_* was the right selection because it tells me something fundamental about the access pattern. That said the word ‘map’ and it’s overlap to ‘map’ in functional programming is a problem. But I digress...
>
>> My point was from an ‘interface’ point of view it’s closest to list. Why is it ‘list like’? First, it’s NOT random access. You have to traverse it. The iterator stability is maintained on modifications. sparse_array might be a good choice — except the dominate features of arrays in c++ is random access and contagious allocation.
>
> I would certainly imagine that a sparse array would try to optimize
> storage for particular values in it, and I don't
> think std::hive does that.
Yes, I see.
>> Let’s take a look at some of the other ‘analogy names’ that have been suggested. I see ‘hotel’, ‘parking lot’, and ‘hive’. I like ‘hive’ very much. Unfortunately, a hive is random access.
>
> If you crack it open. The ones designed to be opened without cracking
> are nests, not hives. :P
> (Or so I read from the internets, hives are natural, nests are
> artificial. Go figure, I don't know whether
> that difference is correct.). The normal access to either isn't
> random, though; bees don't just go directly
> anywhere in the hive or nest, there are some pathways they need to follow.
>
Unfortunately the hexagonal slot pattern is burned into the image of a ‘hive’ — very ordered cells.
>> It’s also a ‘data warehouse’ project - Apache Hive — meh, Java. Building a new floor on the hotel for each block doesn’t really match either — and again, time scales. Parking lot — hmm, I guess you can define linear traversal? It feels like it’s really random access unless it’s one of the Japanese vending machines where you put a car in and it disappears. Ah, but then you use ‘a key’ to get it back — oops.
>
> I have modest disagreement with your time scale problem, because the
> time scales are relative to the lifetimes of the elements,
> not relative to bullet flight times in a game. Thus I think it's a
> mistake to compare a time scale of a building extension to
> that bullet flight, rather than comparing, say, the time scale of a
> hive growing to a lifetime of an occupant of the hive.
That’s fair. The thing is that the ‘fleeting nature’ of elements in a colony is much more like the ‘moving traffic’ that comes and goes than the buildings. Although, to be fair, the use case involves both kinds of elements — some mostly static and some that come and go quickly.
I’m not strongly against ‘hive’ at this point, it’s better than ‘colony’ in my opinion. Just not sure it’s better than block_list or some other function describing variant.
Jeff
>
> On Wed, 10 Feb 2021 at 15:37, Jeff Garland
> <jeff_at_[hidden]> wrote:
>> I don't understand what the term sparse is supposed to tell me about a
>> list. If a list isn't sparse, it's broken.
>> I don’t think of lists as ’sparse’ — they typically have no extra storage. Nodes are allocated and removed as needed. This ‘list’ is special in that it doesn’t immediately deallocate storage when removing an element. It’s a ‘list of allocated slots’. Then it pulls a nifty accounting trick to allow O(N) traversal - a classic time/space trade.
>
> Right. But sparse vs. dense matrices are what I think about when I see
> a suggestion for a sparse list,
> and I don't see how this std::hive (yay, surreptitious sleight-of-hand
> in play, caveat emptor :P) is more
> sparse than a linked list, it seems *less* sparse because there are
> allocated-but-skipped slots in it.
Ok — if I follow you’re saying a ’sparse matrix’ representation would have less storage per unit size than a ‘dense matrix’. Interesting.
>
>> Colony also doesn't behave like a list performance-wise, considering
>> all of its operations, so I don't know
>> why we'd suggest that it's a list.
>> unordered_map doesn’t perform like map either. And as far as I can tell it’s performance properties are unlike any existing container.
>
> Heh, yeah. When pondering about this, I came to a similar conclusion
> that unordered_map and unordered_set aren't
> very descriptive names in some regards.
If there’s a common theme in naming discussions it’s that we can’t get ‘all properties’ in the name. w.r.t. performance, that’s such a complex issue that it seems unlikely we can use it well in naming. std::list ‘in theory’ has certain performance properties based on the number of operations — only problem is modern machines don’t work like old machines -- and so the model is now obsolete, with vector obliterating list in cases where theory would suggest otherwise. My point is that the performance isn’t static over time bc it depends on ever changing machine architectures. So in the case of the names I think unordered_* was the right selection because it tells me something fundamental about the access pattern. That said the word ‘map’ and it’s overlap to ‘map’ in functional programming is a problem. But I digress...
>
>> My point was from an ‘interface’ point of view it’s closest to list. Why is it ‘list like’? First, it’s NOT random access. You have to traverse it. The iterator stability is maintained on modifications. sparse_array might be a good choice — except the dominate features of arrays in c++ is random access and contagious allocation.
>
> I would certainly imagine that a sparse array would try to optimize
> storage for particular values in it, and I don't
> think std::hive does that.
Yes, I see.
>> Let’s take a look at some of the other ‘analogy names’ that have been suggested. I see ‘hotel’, ‘parking lot’, and ‘hive’. I like ‘hive’ very much. Unfortunately, a hive is random access.
>
> If you crack it open. The ones designed to be opened without cracking
> are nests, not hives. :P
> (Or so I read from the internets, hives are natural, nests are
> artificial. Go figure, I don't know whether
> that difference is correct.). The normal access to either isn't
> random, though; bees don't just go directly
> anywhere in the hive or nest, there are some pathways they need to follow.
>
Unfortunately the hexagonal slot pattern is burned into the image of a ‘hive’ — very ordered cells.
>> It’s also a ‘data warehouse’ project - Apache Hive — meh, Java. Building a new floor on the hotel for each block doesn’t really match either — and again, time scales. Parking lot — hmm, I guess you can define linear traversal? It feels like it’s really random access unless it’s one of the Japanese vending machines where you put a car in and it disappears. Ah, but then you use ‘a key’ to get it back — oops.
>
> I have modest disagreement with your time scale problem, because the
> time scales are relative to the lifetimes of the elements,
> not relative to bullet flight times in a game. Thus I think it's a
> mistake to compare a time scale of a building extension to
> that bullet flight, rather than comparing, say, the time scale of a
> hive growing to a lifetime of an occupant of the hive.
That’s fair. The thing is that the ‘fleeting nature’ of elements in a colony is much more like the ‘moving traffic’ that comes and goes than the buildings. Although, to be fair, the use case involves both kinds of elements — some mostly static and some that come and go quickly.
I’m not strongly against ‘hive’ at this point, it’s better than ‘colony’ in my opinion. Just not sure it’s better than block_list or some other function describing variant.
Jeff
Received on 2021-02-10 08:53:53