[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bad things Re: Some thoughts...



Jussi Piitulainen <jpiitula@xxxxxxxxxxxxxxxx> writes:
> David Rush writes:
> > I have just scanned through the SRFI document and a fair bit of the
> > discussion. Just two quick thoughts.
> > 
> > 1) (array-set! a dim0 dim1 ... dimn val) is a *really* bad specification
> >    for this API. Yes, I know it's compatible with vector-set!, but
> >    it's still not right. This form is deeply inefficient, requiring
> >    list packaging of the dimensions (because of the variable length
> 
> Any implementation of a variable number of arguments requires such
> packaging. Yours do, below.

Except that once you've created an indexing object you can also modify
it. Since much array access follows predictable patterns this agains
provides opportunities for significant speed-ups. To summarize:
package once, iterate many. You'll still have the assignments from
loop indicies (unles you macrologize them away with iteration
combinators), but I would be surprised if that took more time than
repeated packaging.

> >    argument list) *and* the value to be placed in the array is bundled
> >    into the same data structure as the indicies.

> In the worst case, if a user really is in a hurry and insists on using
> array-set! and building its argument lists dynamically and then using
> apply, they can stash the values to the end with set-car! to avoid any
> allocation.

But then they have to iterate out to find the cons which will hold the
value. There is just *no way* that having the value to be stored in
the array be the last parameter is a good idea (when you're dealing
with varargs).

> >    either of the following is far better:
> >         1 (array-set! a val dim0 dim1 ... dimn)
> >         2 (array-set! a (array-index dim0 dim1 ... dimn) val)
> 
> Both of these use variable length argument lists. 

But in a loop #2 can do it *many* less times. Multi-dim arrays
*always* get looped over.

> >    I like 2 because of symmetry with the array-shap concept. Also it
> >    has the nice possibility of allowing assignments to larger units of
> >    the underlying array than just single elements.
> 
> I'm rather hoping that array-set! would not be the most common tool in
> practice. 

If you don't want a mutable data structure, then you shouldn't even
let mutability into the spec. I didn't notice any other mutation
operators, am I just blind?

> The latter case here seems more like an array thing already:
> treating an arrangement of values as a unit.

Well, I'd call it a record thing, except for type issues. But yeah.

> > 2) The SRFI should be a completely abstract proposition. There are so
> >    many different array implementations that might be desirable in a
> [...]
> >    for production (I am specifically thinking of numerical & graph
> >    applications here where sparse arrays/matrices can be very common).
> 
> Hm. Could the sharing mechanism be useful with sparse arrays? Perhaps
> it could. I haven't thought of that at all.

Specifically, I'm looking at building a large sparse array of
something like 20,000 x 500,000 elements. The vast majority of those
entries are going to be zero. The rest will have values computed when
they're needed. I'll be obviously implementing all of the
infrastructure for the big arrays myself, but I would like to be able
to test the algorithms on something rather smaller. This is why I'd
like a purely abstract specification.

> >    This means that any vector/array equivalence is a *bad thing* IMO.
> >    Preserve disjointness!

david rush
-- 
With guns, we are citizens. Without them, we are subjects.
	-- YZGuy, IPL