Re: Array appends are quadratic

[Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx>]

On Nov 27,  9:26am, Mikael Magnusson wrote:
} Subject: Re: Array appends are quadratic
}
} According to your debug prints, the array is reallocated every time it
} is assigned to, even when the required element is already allocated.
} Doubling the allocation size would do nothing to fix that, presumably.

Right, this is generic code to handle array splicing, so starting from
an array with 200 elements,

    a[100]=foo

and

    a[50,150]=(foo)

use the same loop even though the former does not change the size of
the resulting array and the latter will waste 100 slots at the top.
I vaguely recall a conversation in which we decided that fewer code
branches was better than attempting to efficiently re-use array slots.


} % a[100]=foo
}  params.c:2585: setarrvalue: Reallocating 'a' to size 100
} % a[5]=bar
}  params.c:2585: setarrvalue: Reallocating 'a' to size 101
} % a[10]=bar
}  params.c:2585: setarrvalue: Reallocating 'a' to size 101
} 
} Do we have an... off-by-two bug somewhere?

No, it just always allocates 1 more than the largest occupied array
index position if the array isn't empty to begin with.