Array `push!` seems to grow amortized O(N)...

[NHDaly]

Average insertion time for inserting n-elements:

Total insertion time for inserting n-elements:

Preliminarily, this behavior seems to be true for both push-front and push-back since 0.5 onwards. Still running the profiles.

[vtjnash]

general array-insert is O(n), only push/pop (e.g. insert at any fixed offset from begin or end) are expected to be O(1)

[KristofferC]

This is normal push! though?

[NHDaly]

So... this is probably an orthogonal, unrelated problem, but @JeffBezanson and I have found that We're manually doing a malloc, memcpy, free every time an array is grown, rather than using realloc:

julia/src/julia_internal.h

Lines 840 to 844 in a2149f8

	void *b = jl_malloc_aligned(sz, align);
	if (b != NULL) {
	memcpy(b, d, oldsz > sz ? sz : oldsz);
	free(d);
	}

This seems to be because there doesn't exist a reasonable method to realloc aligned data, so we have to manually re-do the _aligned_malloc. However, this StackOverflow post suggests that we may be better off attempting a realloc, then testing the resulting alignment, and then only re-doing the _aligned_malloc if it's needed (because the alignment is off):
https://stackoverflow.com/a/9078627/751061

That's especially true when the arrays get huge -- because in that case it's pretty hard to imagine realloc not producing an aligned memory region, so it's probably worth the potential double allocation.

EDIT: This would make it slower, but should be an amortized constant increase, not an order of magnitude increase.

[NHDaly]

Sorry, the problem description wasn't clear. yes, this is push! and pushfront!.

[vtjnash]

So... this is probably an orthogonal, unrelated problem, but JeffBezanson and I have found that We're manually doing a malloc, memcpy, free every time an array is grown, rather than using realloc:

This is still an O(1) operation (and this implementation is better for future threading changes and will be required when switching to the Buffer-based pure-julia Array implementation)

[NHDaly]

This is still an O(1) operation

Yeah, agreed. That's what i meant by this is orthogonal. I shouldn't have qualified that with "probably". Sorry. :)

and this implementation is better for future threading changes and will be required when switching to the Buffer-based pure-julia Array implementation

Huh yeah that's interesting, i'm interested to hear more about that, but that makes sense.

[JeffBezanson]

I still think we should use the technique of calling realloc, checking the alignment, and only copying if necessary. realloc is essential at large array sizes, and at that point also highly likely to be aligned.

[NHDaly]

(I'm happy to branch this conversation to another thread, though, if we want?)

[NHDaly]

So, to continue the original conversation here.

We discovered the actual problem. To summarize what we discussed offline at JuliaCon:

• We came to believe: Arrays grow following the standard "double when full" algorithm, up until a single array uses >= 1% of the computer's RAM, at which point it switches to only growing by exactly the space needed to append the elements! i.e. it grows by one for each insertion if using push!, making each insertion O(N)!

However, upon more investigation with Valentin, we think that's not quite right. The behavior we noticed above should actually be summarized as follows:

• if an array attempts to grow by more than 1% memory, CAP it's growth at 1% of RAM.

And that actually seems somewhat reasonable! That change was introduced here:
139a73a

Now, despite that being significantly more reasonable than we originally thought, I still think that might be somewhat related to the performance described above. It still means that above a certain size, the arrays grow constantly -- just with a much larger constant growth rate than growing by 1. So I think that would still result in an exponential growth of the total cost to insert N elements?

So this still bears some thinking about: is that acceptable?

[NHDaly]

BUT THEN, something else has changed that introduced a significant slowdown in array growth inbetween julia 0.4 and 0.5. As far as I can tell, it's a constant-slowdown of around 1.7x.

We see a pretty big slowdown between 0.4 and 0.5, and it's not related to the above change; the above change was introduced 5 years ago, in julia 0.3.

Here's the plots comparing 0.4-0.7:
https://plot.ly/~nhdaly/1/
https://plot.ly/~nhdaly/3/

In particular, here's the change between 0.4 and 0.5 for push!

0.4 looks deceivingly flat, but it actually has the same shape, just constant-scaled down:

So all of them suffer from this same problem of greater-than-O(1) average time append, but after 5.0 that got slower still. So there's two unrelated "problems" here.

[NHDaly]

Sorry, and just to clarify, the v0.4 to v0.5 regression seems to be always around 2x:

julia0.7> v05[2] ./ v04[2]
>> 6-element Array{Float64,1}:
 2.048994351707916
 1.7865544298045446
 1.1380501128347926
 0.9317471797454173
 0.9720312759644577
 3.3472547019000554

[NHDaly]

So, NEXT STEPS:

1. We should have some kind of quick fix for this problem. I think the simplest thing would be to increase that 1% RAM cap to something like 5%. I think who cares about the asymptotic complexity: it's fine if your growth becomes "quadratic" if there's only going to be at most 20 more growth operations. 100 is kind of a lot, but maybe 20 is okay. or 10. We could do 10% maybe? idk.

2. Find and fix the 2x array growth regression between julia 0.4 and julia 0.5.

3. Investigate other cool growth strategies:

   • we goofed around, talking about other growth functions we could use besides the current discontinuous function: "double until some cutoff, then always add a constant amount". Could we imagine some continuous function that behaves nicely such that it at least doubles -- maybe faster than doubles -- at the beginning, and then tapers off near the end of RAM? Maybe!

[oscardssmith]

what about 1.0? where is that relative to .5?