Re: Pascal Calling Convention

[Hyman Rosen <hyrosen@mail.com>]

On 3/28/2011 6:08 PM, Adam Beneschan wrote:
> On top of that, I don't see why anyone would prefer this over the
> trivial structure that just allocates N bytes, initializes them to 0,
> and sets a byte to 1 to add an element to the set, etc.  That
> structure has non-constant initialization, but so what?
> Initialization will only take place once for a set; the other
> operations are likely to be performed a lot more, and your code
> performs multiple indexed accesses for every operation instead of just
> one.  And the initialization can often be done with a single machine
> instruction.

I didn't invent this data structure - I came across it in a paper and
kept track of it because it made for a very good interview question.
It's a structure no one has ever seen before, it's easy to describe
and it's easy to program the operations. (Needless to say, many of the
people to whom I've given the exercise fail miserably.)

And it's a good program to keep at hand to serve as a counterexample
when programming languages want access to uninitialized data to be
undefined behavior. It's more sensible to regard such data as having
arbitrary but fixed values, subject to a validity check.

The particular need described in the paper was for a kind of graph
where sets of nodes needed to be created and torn down quickly, and
where such a set could potentially have millions of members while it
typically only had a handful. They needed to avoid the initialization
cost of setting many elements to zero, and this is the structure they
invented. (In any case, you can't tell someone to go use an O(N) data
structure when they've told you they want an O(1) one.)