514274 - TM: releaseRegisters, evictRegs scan over all registers [nanojit]

Status: RESOLVED DUPLICATE of bug 584935

(Core :: JavaScript Engine, defect)

Description

[Andreas Gal :gal]

In a bunch of places we can from FirstReg to LastReg manually through the _active table instead of bit-scanning free. This is pretty slow. We should use ffs instead.

Comment 1

[Nicholas Nethercote [inactive]]

I too have been trying to think of ways to avoid this scanning, but I don't think bit-scanning 'free' is the answer.  For one, 'free' and 'active' are not complementary sets, there's also a third category 'unmanaged' which includes things like SP and FP, so you can't assume that active==!free.  Also, in both releaseRegisters() and evictRegs() we need the LIns stored in each slot of 'active'.

I worked up a patch for releaseRegisters that avoided the "if (i)" branch, which Cachegrind says is not easy to predict.  I copied the active LIns values into a secondary buffer, managing to avoid any branches while doing so, and then scanned over this secondary buffer, also avoiding any branches.  It made no noticeable difference.  That's the reality of the situation we're in now, slight improvements to functions that account for less than 1% of execution time are not going to be noticeable.  We have good data for NJ compile-times in bug 514062 but that doesn't mean it's the best thing to focus on.

Comment 2

[Andreas Gal :gal]

I just added proper register state merging instead of just evict-whatever-doesn't-match. The current algorithm is O(n^2). At least for that we probably want a bit scan. I just filed the bug to write down somewhere that the current approach blows. I am not saying making it better will definitively speed us up.

Comment 3

[Nicholas Nethercote [inactive]]

releaseRegisters() and evictRegs() look O(n) to me, where n is the number of regs.
Where does the O(n^2) part come in?

Comment 4

[Andreas Gal :gal]

Register shuffling in merge points is O(n^2) because it uses scanFor. At least there we should consider bitsearch. I just wanted to get it right first, and then we make it fast.