Looks good to me. On Mon, May 11, 2015 at 12:52 PM, Kevin Burton <bur...@spinn3r.com> wrote:
> > I hadn't expected purge() to call heapify(), so I was just expecting O(N) > > runtime for the actual removal. The comments claim the runtime of the > > purge operation is O(N + ClogN) where C is the number of deleted elements > > (which would make it O(N) when C is 1, but looking at the code I think > it's > > actually O(N + ((N-C)/2)log((N-C)/2)), which is O(NlogN) when C is 1. So > > it's not O(N^2), but it's also definitely not O(N) despite the comment's > > claim. > > > > > Yes. I think this is a more appropriate claim. But in my experience it > seems to grow larger than NlogN but perhaps there are secondary issues here > like L1/L2 cache hits that dramatically slow it down > > > > Now I just have it essentially flag the timer task as clear and it will > go > > > through the timer queue and not get executed. > > > > > > > Sounds fine, as long as "flag the timer task as clear" also means "call > > TimerTask.cancel(), so that the task's state will be TimerTask.CANCELLED > so > > it'll be removed the next time it comes to the top of the queue in > > Timer.mainLoop(), in addition to any WeakReference stuff we may do". If > > not, you're going to have a lot of no-op TimerTasks that stick around > > forever, so 1) your value of N will grow over time, so even O(N) > operations > > will take longer over time, 2) there's still an expensive thread context > > switch even if the task is a nominal no-op, and 3) eventually you could > OOM > > due to the memory those no-op TimerTasks take. Does that match what > you've > > implemented? > > > > > Yes. here’s the new cancel method: > > https://gist.github.com/burtonator/6fe3ee640f5f1b27caa2 > > I call task .cancel() then .clear() (which clears the reference). > > and here’s the new SchedulerTimerTask > > https://gist.github.com/burtonator/be4bd7b39c250b2b1a0c > > > -- > > Founder/CEO Spinn3r.com > Location: *San Francisco, CA* > blog: http://burtonator.wordpress.com > … or check out my Google+ profile > <https://plus.google.com/102718274791889610666/posts> >
