Memory management is perhaps the single most performance part of a
database system (at least once you figure out how never touch the
disk). A significant part of the effort on each of my umpteen database
systems has been spent squeezing cycles out of the memory manager, AVL
trees for hunk management, minimizing fragmentation, and eliminating
contention with thread-specific sub-pools.
That said, the NuoDB guys look a fresh look at the problem and evaluated
various other open source memory managers. One, jealloc, was only
slightly slower than my best but did a significantly better job reducing
fragmentation for a clear net gain.
Nikolay's critique is sufficiently well taken that I saw no need to step
into the fray. Still, if there's a better mouse trap with an acceptable
license (jealloc is BSD), why no go for it? Without doubt, the Firebird
memory allocator can be incrementally improved. But unless memory
management is your life's work, if an acceptable open source memory
manager can be shown to be significantly better than what's in place,
adapt it and go on to the next problem.
On 9/19/2014 6:33 PM, Nikolay Samofatov wrote:
> Hello, All!
>
> I implemented intermediate versions GC algorithm and tried to run some stress
> tests on Firebird 3 to
> check if I have broken something.
> The problem is that tests that I created were spending most of their time in
> memory manager. This is
> not healthy.
>
> For example, in my tests I saw up to 300000 iterations in this loop during
> memory allocation:
>
> for (hunk = smallHunks; hunk; hunk = hunk->nextHunk)
> {
> if (length <= hunk->spaceRemaining)
> {
> ....
> }
> }
>
> Dear Firebird engineers, why did you replace an algorithm which has O(log(n))
> performance with an
> algorithm that has O(n) performance in such a performance-critical part of
> the engine?
>
> O(n) performance in certain scenarios was the reason why original memory
> manager of Interbase was
> replaced in Firebird 1.5.
>
> I created a small query to demonstrate the effect of O(n) memory manager
> performance.
> ===
> create table test7 (id integer);
>
> execute block as
> declare variable i integer = 1;
> begin
> while(i <= 50000000) do
> begin
> insert into test7(id) values(:i);
> i = i + 1;
> end
> end;
>
> commit;
>
> savepoint X;
> update test7 set id = id;
> delete from test7;
> ===
>
> Last statement uses 3.5 Gb of memory in small blocks. I forward-ported memory
> manager from Firebird
> 2.5 to Firebird 3 and compared performance of the last statement.
> With Firebird 3 memory manager the query runs for 634 s on my machine. With
> Firebird 2.5 memory
> manger it completes in 427 seconds.
> I used very small number of rows, so you can run it on a desktop class
> machine. It is easy to
> imagine a query that is a couple of orders of magnitude larger in ETL
> applications, and see that
> such queries now become impossible to run (due to at least an order of
> magnitude estimated slowdown).
>
> So the performance of the server is now O(N^2) for queries using large
> amounts of memory, and the
> server hits the wall rather quickly.
>
> From quick review of new memory manager code I can see the following
> problems:
> 1) O(n) performance in small hunk allocation
> 2) O(n) performance in large hunk deallocation
> 3) Worst case allocation cost in large hunk allocation algorithm is bounded,
> but much worse than for
> older memory manager
> 4) Lots of memory waste in various scenarios, which is a security issue with
> mild risk.
> 5) Not all debug facilities have been preserved.
>
> Problem 1 and 2 can be relatively inexpensively fixed with existing code
> base. Are there volunteers?
> Problems 3 and 4 require going back to global best-fit allocation strategy,
> and thus re-design.
>
> Alternatively, I may fix Firebird 2.5 memory manager to have better
> performance in simple cases
> without compromising worst-case performance.
> This is rather easy. B-Tree can be replaced with specially designed array of
> pointers (see FastMM
> code, for example).
> Dmitry, do you want me to do this?
>
> My understanding is that Firebird project probably does not care about large
> installs and security,
> so it will continue using new memory manager as it is marginally faster in
> simple cases. For Red
> Database version based on Firebird 3 we shall certainly back out this memory
> manager as it has
> unpredictable performance and introduces new security risks.
> Good thing is that changing or replacing memory manager is very simple task
> for existing code base.
>
>
> Best Regards,
> Nikolay Samofatov
>
>
> ------------------------------------------------------------------------------
> Slashdot TV. Video for Nerds. Stuff that Matters.
> http://pubads.g.doubleclick.net/gampad/clk?id=160591471&iu=/4140/ostg.clktrk
> Firebird-Devel mailing list, web interface at
> https://lists.sourceforge.net/lists/listinfo/firebird-devel
------------------------------------------------------------------------------
Slashdot TV. Video for Nerds. Stuff that Matters.
http://pubads.g.doubleclick.net/gampad/clk?id=160591471&iu=/4140/ostg.clktrk
Firebird-Devel mailing list, web interface at
https://lists.sourceforge.net/lists/listinfo/firebird-devel
