499359 - code alloc should use a freelist so allocation is O(1) on average

Status: VERIFIED FIXED

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect)

Description

[Edwin Smith]

current impl walks all the pages on every alloc, which gets expensive when there are lots of pages.

Comment 1

[Tom Harwood]

Easily done via freelist; segregated freelists would also be goodness if we have any allocation data.

Comment 2

[Edwin Smith]

this allocator is unique because the client doesn't know how much memory it needs; it can use whatever block size is returned, above a minimum size (which is the parameter to alloc()).  so theres reason to be optimistic that a simple any-block-will-do freelist is enough.

Comment 3

[Lars T Hansen]

If the client can make a really cheap guess that's in the ball park more often than not then the allocator could conceivably make use of that to find a good block.  Maybe that's for version 2 though :-)

Comment 4

[Tom Harwood]

Attachment: Proposed patch

Comment 5

[Edwin Smith]

any reason to be concerned with the O(N) traversal to remove a block from the free list when it gets coalesced with a neighbor?  at the moment, tamarin-redux doesn't really free code much, so probably not.  possible fix would be to make the freelist doubly linked.  (doubly more tricky pointer code, but cheap since the back pointer can be overlapped with the data area of a block).

Comment 6

[Tom Harwood]

re: comment #5, I wrote doubly-linked list code and then tore it out.  Two reasons:

1.  The length of the avail list is much shorter than the length of the master list;
2.  This coalescing code was not executed in any of the more-complex testcases I have readily to hand (i.e., utils, esc,  various optimizer tests).  In fact, thanks for reminding me I need to circle back and check with you and QE to get a testcase, I presume we do have testcases that exercise it...

Comment 7

[Edwin Smith]

(In reply to comment #6)
> re: comment #5, I wrote doubly-linked list code and then tore it out.  Two
> reasons:
> 
> 1.  The length of the avail list is much shorter than the length of the master
> list;
> 2.  This coalescing code was not executed in any of the more-complex testcases
> I have readily to hand (i.e., utils, esc,  various optimizer tests).  In fact,
> thanks for reminding me I need to circle back and check with you and QE to get
> a testcase, I presume we do have testcases that exercise it...

cool. simple is good.  the only way to really exersize free() is to make code get unloaded, which can be (is?) convoluted.  we might be able to build a self-test harness that runs the 2nd phase of the jit N times.

testing within the (old) thrashy jit-cache code would work too but will take a lot of rebasing to get to a testable state.

Comment 8

[Chris Peyer]

http://hg.mozilla.org/tamarin-redux/rev/0d84abb30180