Horrible performance for GIF with many frames

https://github.com/nothings/stb/blob/f1c79c02822848a9bed4315b12c8c8f3761e1296/stb_image.h#L6963

This function stbi__load_gif_main() is doing a lot of pointless realloc() and pointless copying while constructing final buffer in what is essentially an $O(N^2)$ operation.

For example a simple 406x406 pixels GIF with 278 frames and 256 colors takes 5,843 ms to decode on a 12-core Xeon w5-2455X running at 4.6 GHz.

Most of that exorbitant time is spent reallocating memory and copying already decoded frames and growing the delays array.

To put it simply, it moves $\approx 50.96 \text{ GB}$ to decode those 278 frames which are only 174.8 MB total when decoded (659,344 bytes per frame).

I did a quick test implementation which uses std::vector<stbi_uc*> for book-keeping allocations for individual frames and std::vector<int> for delays and then coalescing all at once at the end while freeing individual frames.

The result is a staggering 12.6x speedup in decoding that very same file (462 ms instead of 5,843 ms).

The code change I made, if anyone is interested — it reduces memory moves to $\approx 550.04 \text{ MB}$ down from $\approx 50.96 \text{ GB}$ thus reducing memory bandwidth usage by $92.6\times$ by turning decoding into an $O(N)$ operation:

static void* stbi__load_gif_main(stbi__context* _Ctx, int** _Delays, int* _X, int* _Y, int* _Z, int* _Comp, int _ReqComp)
{
	if (stbi__gif_test(_Ctx)) {
		int Layers = 0;
		stbi_uc* U = nullptr;
		stbi_uc* TwoBack = nullptr;
		stbi__gif G;
		int Stride = 0;

		std::vector<stbi_uc*> FramePointers;
		std::vector<int> DelayValues;

		memset(&G, 0, sizeof(G));

		do {
			U = stbi__gif_load_next(_Ctx, &G, _Comp, _ReqComp, TwoBack);
			if (U == (stbi_uc*)_Ctx) {
				U = nullptr;
			}

			if (U != nullptr) {
				*_X = G.w;
				*_Y = G.h;
				Stride = G.w * G.h * 4;

				stbi_uc* FrameData = (stbi_uc*)stbi__malloc(Stride);
				if (FrameData == nullptr) {
					for (stbi_uc* P : FramePointers) {
						STBI_FREE(P);
					}
					return stbi__load_gif_main_outofmem(&G, nullptr, _Delays);
				}

				memcpy(FrameData, U, Stride);
				FramePointers.push_back(FrameData);
				DelayValues.push_back(G.delay);

				Layers = (int)FramePointers.size();

				if (Layers >= 2) {
					TwoBack = FramePointers[Layers - 2];
				}
			}
		} while (U != nullptr);

		STBI_FREE(G.out);
		STBI_FREE(G.history);
		STBI_FREE(G.background);

		if (FramePointers.empty()) {
			return nullptr;
		}

		size_t TotalSize = (size_t)Layers * Stride;
		stbi_uc* Out = (stbi_uc*)stbi__malloc(TotalSize);

		if (Out != nullptr) {
			for (int i = 0; i < Layers; ++i) {
				memcpy(Out + (i * Stride), FramePointers[i], Stride);
				STBI_FREE(FramePointers[i]);
			}

			if (_Delays != nullptr) {
				*_Delays = (int*)stbi__malloc(Layers * sizeof(int));
				if (*_Delays != nullptr) {
					memcpy(*_Delays, DelayValues.data(), Layers * sizeof(int));
				}
			}
		}

		if (_ReqComp != 0 && _ReqComp != 4) {
			Out = stbi__convert_format(Out, 4, _ReqComp, Layers * G.w, G.h);
		}

		*_Z = Layers;
		return Out;
	} else {
		return stbi__errpuc("not GIF", "Image was not as a gif type.");
	}
}

I am aware that the goal of this library is portability and simplicity and is limited to C99 so std::vector is out of the question, but still the same principle I used here with std::vector (and I did it just for simplicity as a quick hack) can be used to speed it up without it — you can keep realloc()-ing an array of pointers to decoded frames instead of reallocating and copying growing chunk of memory and putting pressure on both CPU cache and heap manager.

Which ever way you slice it, at the frame 277 in my example both code versions need 2x the memory to make the final merged buffer so the original function isn't even memory efficient — it simply has no redeeming qualities.

Another thing that could be done better is stbi__gif_load_next() already gets ReqComp, why make a final pass for 4->3 channels conversion if you can do it per frame right at the start.

Moreover, background and history buffer copies can also be avoided if pointers are used (which would be a benefit of this proposed change).

Finally, the decoding itself could be improved as well but this is a low effort fix IMO. I hope the maintainers consider it.