GNU bug report logs - #65491
[PATCH] Improve performance allocating vectors

Previous Next

Full log

View this message in rfc822 format

From: Mattias Engdegård <mattias.engdegard <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 65491 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: bug#65491: [PATCH] Improve performance allocating vectors
Date: Mon, 25 Sep 2023 18:06:37 +0200

> - Reducing the `vector_free_lists` array to its actually used first half does improve performance a bit, even with subsequent scanning speed-ups.

> - The previously mentioned hack where scanning begins in the most recently added bucket is surprisingly effective, often even more so than a bitmap, but I'm wary of it being brittle. Need more measurements.

These two changes were simple, fairly effective, and found to be reasonably safe (in the sense that they are unlikely to make performance worse), so I pushed them to master. This way we should be better off even if no further progress is made.

As mentioned, a bitmap is essentially as good as or better than the last-used-index heuristic but I went with the latter because it involved a lot less code. This can be changed.

But it is possible to do better: size-homogeneous blocks, where each block only houses vectors of a single size, have the major benefit that live_small_vector_holding no longer needs to traverse half the block on average but becomes is done in constant time. Sweeping, always performance-critical since it traverses both living and dead objects, becomes slightly faster. There is also no free-list array scanning at all.

Benchmarks suggest that larger homogeneous blocks (32 KiB, say) would be beneficial, but we need to look at the potential extra fragmentation caused by allocating a big block for each odd vector size.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.