From: Matthew Kerwin Date: 2012-11-15T11:29:09+09:00 Subject: Re: Extending Array instances --f46d042f939866c3c304ce7f6a94 Content-Type: text/plain; charset=ISO-8859-1 On 15 November 2012 06:48, Charles Hixson 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 --f46d042f939866c3c304ce7f6a94 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On 15 November 2012 06:48, Charles Hixson <charleshixsn@earthlink= .net> wrote:
Sorr= y, my C isn't that good, and there are a lot of undefined terms in that= snippet. =A0I can't really say I understand it. =A0I 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= . =A0For that matter, I usually avoid macros, too. =A0I realize that this i= s a common C coding style, but it's one reason I dislike C. =A0I'd = prefer D, FORTRAN, or even Ada or Eiffel. =A0(Yaa...the code is what it is.= =A0But 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 a= void 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 don= e in it, and actually quite simple when you're thinking at the C level.= =A0It's not a coding style, it's how C works. =A0And yes, without = pointers preallocated arrays will often be faster than everything else, bec= ause without pointers you're losing the ability to do operations like m= emory copying and collection restructuring and object comparisons by refere= nce; 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:

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

=A0 =A0 =A0 =A0 =A0if (new_capa< =A0ARY_DEFAULT_SIZE) { /* clamp t= o some globally defined minimum */
=A0 =A0 =A0 =A0 =A0 =A0 =A0new_capa =3D ARY_DEFAULT_SIZE; =A0/* (e.g. d= on't extend by 3, when 512 would be more sensible?) */
=A0 =A0 =A0 =A0 =A0}
=A0 =A0 =A0 =A0 =A0if (new_capa>=3D= ARY_MAX_SIZE - idx) { /* clamp to some globally understood maximum */
=A0 =A0 =A0 =A0 =A0 =A0 =A0new_capa =3D (ARY_MAX_SIZE - idx) / 2; /* i.= e. half the available maximum space */
=A0 =A0 =A0 =A0 =A0}
=A0 =A0 =A0 =A0 =A0new_capa +=3D idx;<= /span>
=A0 =A0 =A0 =A0 =A0REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa); /* = some realloc() macro -- looks exactly like realloc() to me */
=A0 =A0 =A0 =A0 =A0RARRAY(ary)->aux.capa =3D new_capa; /* tell the a= rray what its auxiliary capacity has become */
=A0 =A0 =A0}


If I design the= basic framework of the application around a poor design, I'll have to = rewrite the entire thing. =A0This is something to get right at the start. = =A0It's not a premature optimization. =A0There are lots of places where= I'm taking to "do enough and patch it later" approach. =A0Th= e 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.=A0Which container you're using isn't part of that a= lgorithm.

Again: which = container you're using isn't part of the algorithm, especially in a= n OO context like Ruby. =A0In the algorithm you say "add to the contai= ner" or "look up thingy in the container." =A0Then when you&= #39;ve implemented it, if the algorithm is gravy but execution takes too lo= ng, maybe think about alternative _containers_, based on how your (already = good) algorithm is using it. =A0E.g. sparse storage suggests not using an a= rray, random inserts but sorted iteration implies some sort of heap or some= thing, etc. =A0The main point is, the outer algorithm is the big deal; you = abstract the container with a little black box called "the container&q= uot; until you know more about how the whole system works.

Ruby is a hig= h enough level language that you can abstract the container's inner wor= kings like this safely. =A0It's also high enough that you can't rea= lly predict the behaviour without _trying_ it (or without having written do= zens of other similar programs and getting a feel for how various objects b= ehave.)

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

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

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