Closed Bug 416717 Opened 16 years ago Closed 11 years ago

O(1) arena release

Categories

(Core :: JavaScript Engine, enhancement, P4)

Product:
Core
Component:
JavaScript Engine
Type:
enhancement

Tracking

()

Status:
RESOLVED DUPLICATE of bug 851627

People

(Reporter: igor, Assigned: moz)

Details

(Keywords: perf) 

[This is a spin-off of bug 416628 comment 10]

Currently JS_ARENA_RELEASE(pool, mark) can be O(n) in time where n is the number of allocated arenas since the mark. This is due the need to search the linked list of arenas for the arena holding a mark.

It would be nice to make sure that the search time is O(1) to prevent bugs like 416628 from happening. It can be implemented, for example, via storing (areana, offset) pair as a mark as such arrangement allows to add the freed arenas to the the free list in O(1) time.
Flags: blocking1.9+
Priority: -- → P2
Flags: blocking1.9+
Keywords: perf
I am modifying jsarena code, now, for another bug, and the arena release code hurts my eyes!  We should avoid this O(n) arena release algorithm before it bites us.

Please assign the bug to me.  Set the priority and milestone flags as you deem fit.

Taking this bug.  I am making it P4.  Let me know if you disagree (Igor?).
Status: NEW → ASSIGNED
Priority: P2 → P4
Assignee: general → moz
Status: ASSIGNED → NEW
igor, is this still relevant?
(In reply to comment #3)
> igor, is this still relevant?

From the source JS_ArenaRelease I see that the code still uses O(N) loop. So the bug is still relevant.
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.