[PD] [PD-announce] getpatchname

[Mathieu Bouchard]

On Thu, 13 Jul 2006, Miller Puckette wrote:
> On Wed, Jul 12, 2006 at 10:15:53PM -0400, Mathieu Bouchard wrote:
>> On Wed, 12 Jul 2006, Miller Puckette wrote:
>>> The usual reason: my reluctance to add bloat to data structures...
>> Yeah right. If you really cared about "bloat" you wouldn't be abusing
>> linked-lists the way you do.
> Hmm, how am I abusing linked lists?  If there's a cleaner way to manage
> them than I'm doing, I should learn it :)

This is relative. In January I've upgraded a machine from 512M to 1024M 
just so that I could compile a program within reasonable delays (avoid 
swapping RAM to disk). This cost me something approx 80 CAD (72 USD or 56 
EUR).

In the light of this, "Wasting" 4 or 8 bytes per object (and then, only 
the ones that don't already have a t_canvas backpointer) doesn't seem like 
a big deal.

In DesireData, a lot more is "wasted" because each object has a helper 
struct attached to it with several fields in it ("observers", "dirties", 
"visuals", and such). Possibly that no-one will ever complain about the 
size of those things.

Linked-lists waste memory compared to arrays because each element requires 
both an extra pointer and a malloc, and the cost of one malloc itself is 
equivalent to a few pointer-sized variables. RAM amounts don't matter so 
much, I was only saying that to make a point about "bloat". However there 
are other downsides of linked-lists that you may want to care about: cache 
locality and algorithmic time.

Cache locality is a problem because you don't control where your mallocs 
are, so in the worst case a linked list may have each of its 
elements in a different memory block, which makes it look like 
it's taking several dozen times more RAM than it really does, in terms of 
time that the CPU spends downloading RAM.

Algorithmic time is relevant only for long lists. E.g. appending 1000 
elements one at the time at the end of a linked list while keeping on 
forgetting the pointer to the last element. This takes 500000 steps 
instead of 1000. Similar things may happen with non-linked lists, e.g. 
list messages that have to be copied all of the time just to add one 
element, end up taking 500000 steps if [list] appends single elements 
1000 times.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montréal QC Canada