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