1354616 - Removing timers (due to firing or cancellation) can be really slow)

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Boris Zbarsky [:bzbarsky]]

I just had my browser acting very slowly, mostly because I left about:performance running for too long, I think, and it got really slow.

I profiled it, and there was a bunch of timer stuff happening (GC, etc, etc), but the thing that jumped out at me is that in the chrom process we spent a _lot_ of time in TimerThread::RemoveTimerInternal.   And when I say a lot, I mean 25% of the chrome-process samples were in this function, for a total of 2.5s of runtime.

The problem, I assume, is that I had a ton of outstanding timers (e.g. because they were being throttled?) and RemoveTimerInternal ends up doing O(N) work, either in finding the right timer or in the resulting memmove.

The problem is that I'm not sure which it is, an the profiler won't tell me.  If it's finding the right timer, seems like we could RemoveElementSorted, right?  But if it's the memmove, then I'm not sure how best to deal, because switching to a linked list will make it hard to do binary sort insertion.

Looking at the profile, most of the removals are coming from nsTimerImpl::Cancel, and the rest from nsTimerImpl::InitCommon.  So I suspect it's the finding bit, especially for the latter: in that case the timer is kinda known to not be in the list!

Nathan, can you see a problem with using RemoveElementSorted in RemoveTimerInternal?

Comment 1

[Boris Zbarsky [:bzbarsky]]

Profile link: https://perf-html.io/public/c7a84271214fa3d9b2df4bc762d74333975a9782/calltree/?thread=0

Comment 2

[Nathan Froyd [:froydnj]]

(In reply to Boris Zbarsky [:bz] (still a bit busy) (if a patch has no decent message, automatic r-) from comment #0)
> Nathan, can you see a problem with using RemoveElementSorted in
> RemoveTimerInternal?

I don't--we only ever insert sorted, and we ought to be able to remove sorted, too.

FWIW, bkelly had a small patch series to optimize how we store things in bug 1325254.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Ah, looks like the "Make nsITimer::Cancel() O(c)" patch there would effectively address this...

Comment 4

[Nathan Froyd [:froydnj]]

I'm going to assign this just for tracking purposes, but bz was going to look into polishing up the patches for bug 1325254.

Comment 5

[Nathan Froyd [:froydnj]]

There's nothing left to do here now that the dependent bug has landed, correct?

Comment 6

[Boris Zbarsky [:bzbarsky]]

I believe that's correct, yes.