Use queue instead of stack

[dpsanders]

No description provided.

[eeshan9815]

@dpsanders Can you please point me to the place in the codebase this needs to be changed?

[dpsanders]

This refers to the data structure used to store the boxes as they are processed, and in particular the order in which they are processed. Currently they are placed onto the vector with push! and removed with pop! (?) which gives a stack (last in, first out). This comment was along the lines of using a queue instead (first in, first out).

…

On Thu, 8 Mar 2018, 9:29 am Eeshan Gupta, ***@***.***> wrote: @dpsanders <https://github.com/dpsanders> Can you please point me to the place in the codebase this needs to be changed? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#22 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AALtTkIlTUOqwUhy7_rJ6utcccxJUVImks5tcU5MgaJpZM4OGI1V> .

[dpsanders]

This gives breadth-first vs depth-first search of the tree of boxes that gets created.

[gwater]

I think we should decide what the desired outcome of each strategy is.

memory In many cases depth-first strategy should be more memory efficient because after an interval is bisected its sub intervals are immediately pruned and quickly vanish from memory. A breadth-first search would bisect many intervals before eventually pruning their sub intervals, leading to potentially large fluctuations in queue size.

time Both strategies should have identical speed on a single process. However, depth-first will find Roots more periodically throughout the iteration, whereas breadth-first will find most roots close to the end of iteration.

parallelism However, a breadth-first strategy might be useful for a parallelized implementation. In that model work intervals should be bisected as early as possible to fill a task queue which can feed many worker processes. (Of course it would also look very nice in a visualization to watch intervals split, vanish and shrink in parallel. But aesthetics are probably irrelevant to most users.)

Did I miss something?

[dpsanders]

Thanks, that sounds like a good analysis.

I think I was thinking more for optimization, where I think that breadth-first should be better.

[Kolaru]

I was thinking about #59 and I realized that in the case of an accumulation of many zeros (for example with x -> sin(1/x) near 0) the maximal number of intervals must be limited, but also bread-first or depth-first searches would result in very different outputs (still using sin(1/x) as an example):

• Depth-first search will find many negative zeros, but one of the output will be Root(0..+Inf, :unkown).
• Breadth-first search will more or less find zeros uniformly.

Ideally both should be implemented, and it may be possible to even allow the user to provide a function to choose the next interval to be bisected (as a parameter of the RootSearch object for example, since it is low level tweeking).

[Kolaru]

I am currently working on this (I let you know to avoid the work being done twice).

In fact I am trying to implement something more general, where the user can provide a data structure (currently we use Vector), a method to store the intervals (currently push!) and a method to get them (currently pop!).

[gwater]

It might be more user friendly to provide a set of specific strategies, rather than an abstract interface. (Of course an internal abstraction layer could still make sense.) I think a new dependency on DataStructures.jl would make that very simple.

[Kolaru]

Fixed by the introduction of BreadthFirst and DepthFirst search strategy.