Faster y-range sorting

[goodboy]

After #302 lands there are 2 main sources of latency left in chart interaction:

• redraw latency (a much larger task to deal with that will require further extensions to our Rendering sub-systems) that contains:

  • maybe a downsampling of data via m4
  • a delete and redraw of a QPainterPath for the data in view

• max() / min() sorting of the y-data in-view

  • currently we naively use np.max()/.min() and very basic x-range caching inside our Flow type
  • the display loop will also naively call this same method on updates, which if there's conditions to actually redraw a large (1M datums +) entire graphic in view, can be quite slow

In order to see this latency in action pass a --profile 10 to your piker chart command to see something like:

 > Entering `ChartView._set_yrange()`: `dolla_vlm`
    callback ._maxmin(): (0, 22800345.0): 24.8241 ms
    set limits: (-1368020.7, 24168365.7): 0.1694 ms
  < Exiting `ChartView._set_yrange()`: `dolla_vlm`, total time: 24.9964 ms
    > Entering `<piker.ui._chart.ChartPlotWidget object at 0x7f8b66fcae60>.maxmin(name=trade_rate)`: `volume`
      volume got bars range: 0.0380 ms
      yrange mxmn: (0, 1299940) -> (0.0, 0.0): 16.0576 ms
    < Exiting `<piker.ui._chart.ChartPlotWidget object at 0x7f8b66fcae60>.maxmin(name=trade_rate)`: `volume`, total time: 16.1166 ms
    > Entering `<piker.ui._chart.ChartPlotWidget object at 0x7f8b66fcae60>.maxmin(name=dark_trade_rate)`: `volume`
      volume got bars range: 0.1704 ms
      yrange mxmn: (0, 1299940) -> (0.0, 0.0): 12.8711 ms
    < Exiting `<piker.ui._chart.ChartPlotWidget object at 0x7f8b66fcae60>.maxmin(name=dark_trade_rate)`: `volume`, total time: 13.0730 ms
  > Entering `ChartView._set_yrange()`: `trade_rates`
    callback ._maxmin(): (0, 0): 29.5531 ms
    set limits: (0.0, 0.0): 0.2536 ms
  < Exiting `ChartView._set_yrange()`: `trade_rates`, total time: 29.8102 ms

---

Strategy to solve this: demire?

• the demire streaming algo would be one impl to test which generates mx/mn output arrays for each window step:
  • py code: https://github.com/lemire/pythonmaxmin/blob/master/maxmin.py
  • an interesting though i had is that if you wanted to do a single pass of historical data you can in theory compute the mx/mn output for every higher level window size by recursively apply the algo on past outputs (i'll have to write more details on this thinking, but), in which case we could more or less build a sequence cache of (window_size: int, lag: int) which could be used to do a cache lookup for every zoome level? Def needs more deep thought.
  • this might play well into our usage of trend calculus which requires more or less the same mx/mn computations but is agnostic to the runtime efficiency of these ops in the original paper.
• exponential search techniques?
  • wiki: https://en.wikipedia.org/wiki/Exponential_search
  • eg code snippet: https://www.geeksforgeeks.org/exponential-search/

[goodboy]

this should help drive https://github.com/goodboy/tractor/issues/175 as well