On 09/20/14 10:58, Dmitry Yemanov wrote: > Nickolay, > >> 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. > Out of curiosity, what is the call sequence that leads to the memory > manager load? AFAIU, this is not what should normally happen when > processing records. Maybe post_verb / verb_cleanup? > >> 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? > Maybe because you're speaking just about one case while there are other > cases when the new memory manager was proven to be more efficient? I > hope Alex will jump in with more details.
Current memory manager was ported from Vulcan a few years ago, at the most beginning of FB3 project. Certainly the first thing to do was performance comparison. I've tries on fbtcs, backup/restore of some real life databases, tpc/c and something else. Unfortunately I did not save results for all tests and I do not remember them now - too many time has gone, but speedup for all tests was between 5 and 10 percents, and certainly none of them showed worse performance. Certainly I knew about O(n) performance issues, but that time performance growth appeared enough for me, and I've decided to return to that issue later. Looks like time for it came. >> 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. > Do you mean the undo log here? vct_records bitmap of 3.5GB? > >> 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? > I would warn against any quick decisions. Let's wait for Alex's comments > first. I see no problems with any solution as long as it provides better performance. I myself planned to port to Fb3 memory manager from 2.5 at least initial allocation of memory from parent memory pool. Obvious step to try is also changing stepping if tiny blocks sizes from const to something more interesting (like in mentioned FastMM for example). From what we see here better approach instead of linear linked list is required for smallhunks. And looking at this list I start to wonder - may be it's really better to port tiny blocks allocation into 2.5 memory manager? >> Good thing is that changing or replacing memory manager is very simple task >> for existing code base. > I'd rather prefer the memory manager being replacable / pluggable at > runtime. Quite possible, very useful, requires low programming efforts. > This is not about FB3 though. Unfortunately you are absolutely right. ------------------------------------------------------------------------------ Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk Firebird-Devel mailing list, web interface at https://lists.sourceforge.net/lists/listinfo/firebird-devel
