Re: Extending Array instances

On 15 November 2012 06:48, Charles Hixson <[e-mail]>wrote:

> Sorry, my C isn't that good, and there are a lot of undefined terms in
> that snippet.  I can't really say I understand it.  I can usually guess
> what's going on, but undefined macros make me quite unsure...and I try to
> avoid pointers when writing code, because I want to understand it later.
>  For that matter, I usually avoid macros, too.  I realize that this is a
> common C coding style, but it's one reason I dislike C.  I'd prefer D,
> FORTRAN, or even Ada or Eiffel.  (Yaa...the code is what it is.  But to me
> what it is is confusing.)
>

This is going to sound elitist and snobby, but I'm pretty sure that's the
whole problem right there. If you avoid pointers in C because they're
confusing, then do not ever write C. Pointers are a fundamental part of the
language and how you get things done in it, and actually quite simple when
you're thinking at the C level.  It's not a coding style, it's how C works.
 And yes, without pointers preallocated arrays will often be faster than
everything else, because without pointers you're losing the ability to do
operations like memory copying and collection restructuring and object
comparisons by reference; reading and writing entire objects is always slow.

I don't know the Ruby C API at all, but my guess at interpreting the
snippet would be:

    if (idx>= RARRAY(ary)->aux.capa) {  /* if the index is beyond the
RARRAY (Ruby Array)'s auxiliary capacity (i.e. total allocated space?) */
        long new_capa = RARRAY(ary)->aux.capa / 2; /* new_capa = current
capa / 2 */

         if (new_capa<  ARY_DEFAULT_SIZE) { /* clamp to some globally
defined minimum */
             new_capa = ARY_DEFAULT_SIZE;  /* (e.g. don't extend by 3, when
512 would be more sensible?) */
         }
         if (new_capa>= ARY_MAX_SIZE - idx) { /* clamp to some globally
understood maximum */
             new_capa = (ARY_MAX_SIZE - idx) / 2; /* i.e. half the
available maximum space */
         }
         new_capa += idx;
         REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa); /* some realloc()
macro -- looks exactly like realloc() to me */
         RARRAY(ary)->aux.capa = new_capa; /* tell the array what its
auxiliary capacity has become */
     }


If I design the basic framework of the application around a poor design,
> I'll have to rewrite the entire thing.  This is something to get right at
> the start.  It's not a premature optimization.  There are lots of places
> where I'm taking to "do enough and patch it later" approach.  The reason
> this isn't one, is because this needs to be handled now.


Indeed. Write the algorithm. Optimise the algorithm. Make sure you're using
sensible algorithmic techniques. Which container you're using isn't part of
that algorithm.

Again: which container you're using isn't part of the algorithm, especially
in an OO context like Ruby.  In the algorithm you say "add to the
container" or "look up thingy in the container."  Then when you've
implemented it, if the algorithm is gravy but execution takes too long,
maybe think about alternative _containers_, based on how your (already
good) algorithm is using it.  E.g. sparse storage suggests not using an
array, random inserts but sorted iteration implies some sort of heap or
something, etc.  The main point is, the outer algorithm is the big deal;
you abstract the container with a little black box called "the container"
until you know more about how the whole system works.

Ruby is a high enough level language that you can abstract the container's
inner workings like this safely.  It's also high enough that you can't
really predict the behaviour without _trying_ it (or without having written
dozens of other similar programs and getting a feel for how various objects
behave.)

So again, in summary: write the part of the algorithm you can control, and
make it as good as can be. Then use empirical testing to find the best
objects to fill in those black boxes.

-- 
  Matthew Kerwin, B.Sc (CompSci) (Hons)
  http://matthew.kerwin.net.au/
  ABN: 59-013-727-651

  "You'll never find a programming language that frees
  you from the burden of clarifying your ideas." - xkcd