Re: Proposal: block-based vector allocator

[Stefan Monnier]

>> Is that more or less what you had done?  It's a very standard and
>> popular malloc algorithm, so I'm surprised you say it didn't work well.
> The point is that it makes no sense to have 'standard malloc algorithm'
> for vector allocation on top of another 'standard malloc algorithm' used
> by C library malloc. To get an advantage over plain malloc()/free() pair,
> we should have something specially tailored for our needs instead of
> duplicating library functionality at the higher levels.

Then I suggest you leave the code alone: we have no evidence that the
allocation pattern of vectors is any different than what malloc was
designed for, and the malloc library has seen many years of engineering
and tweaking, so you're very unlikely to do better than it does.

> Any good allocator should be a well-designed balance between
> complexity, speed, code size, fragmentation, etc.,

Yes.  And the design I propose is one that has proved to be such a good
balance.

> but I'm trying to target smallest possible fragmentation and best
> possible heap utilization with smallest possible waste.

Then you're doing it wrong: do it the way Lisp_Strings are handled
(i.e. with compaction).

>> So we should have a fair bit of wiggle room here.  Especially since I'm
>> not specifically interested in reducing memory use as much as getting
>> rid of the O(log n) overhead and generally making smallish
>> "defstruct-style" vectors more efficient.
> This approach looks pretty strange for anyone who looks through this list's
> archives: "my Emacs is too slow" noise is quite rare, but "my Emacs is
> too fat" topics are raised over and over again.

The intention is not to make Emacs faster, but to eliminate gross
inefficiencies on particular operations (because that can influence
coding style negatively).

> I believe Emacs is fast enough to be a good editor on any
> reasonable hardware.

I disagree (it often has trouble keeping up with my typing (and I don't
even touch-type); but of course, this particular optimization won't
help, since the slowness is mostly in the display rendering which is not
affected by the speed of vector allocation).

> Even for an instance bloated with a few hundreds of buffers, I never seen
> a GC longer than 0.1s, which is faster than a keystroke.

None of this is related to the GC speed anyway.


        Stefan