Re: Question about sparse arrays/atomic operations in systemtap

[Alan Conway <aconway at redhat dot com>]

On Tue, 2014-06-03 at 08:46 -0700, Josh Stone wrote:
> On 06/03/2014 08:30 AM, Josh Stone wrote:
> > On 06/03/2014 06:34 AM, Alan Conway wrote:
> >> Another way to solve it (which might have more general use) would be to
> >> have a new array type: a 'sparse array' which automatically deletes
> >> values when they are set to the array default (0, "", empty statistic
> >> etc) Such an array type would be very useful for arrays that are
> >> potentially huge (e.g. an entry for every mutex in a process) but are
> >> mostly 0.
> >>
> >> Is there already a solution to this problem in systemtap, or would the
> >> sparse array be a useful addition?
> > 
> > This might still be a useful feature for brevity and performance.  I'll
> > have to check, but ISTR the map runtime even has a flag to do this
> > already, so we'd just have to express that desire somehow.
> 
> Just a quick followup, I think there might be a misconception behind
> calling this a "sparse array" -- they're all actually maps, even when
> your indexes are integers, so there's no waste for gaps in indexes.
> 
> But auto-deleting would not help if you want to still represent entries
> as present-but-zero.  Presence will satisfy the "in" operator, but once
> deleted that returns false.  Remembering zeroed keys so that they are
> still "in" means we have to keep those keys stored somewhere.
> 
> So delete-on-zero is possible, but that wouldn't preserve "in".
> 

Yes, understood. The case I'm thinking about is where you are keeping
counters on a potentially large number of objects (e.g. mutexes) where
the the counters are mostly zero at any given time. That's what I mean
by "sparse" - not just that it is a map but a step further, we need to
actively remove 0 entries because otherwise we overrun array limits with
stuff that was once non-zero but is now 0 and no longer interesting.

As you point out in your last mail, systemtap is doing all the required
locking so doing this by hand is fine - an automatic "sparse" array
might be a useful convenience but is not a necessity.

Cheers,
Alan.