Codecov Report

Merging #2810 (b830410) into master (e0fd830) will decrease coverage by 0.36%.
The diff coverage is 90.62%.

@@            Coverage Diff             @@
##           master    #2810      +/-   ##
==========================================
- Coverage   91.79%   91.43%   -0.37%     
==========================================
  Files         146      147       +1     
  Lines       11192    11352     +160     
==========================================
+ Hits        10274    10380     +106     
- Misses        918      972      +54     

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update e0fd830...b830410. Read the comment docs.

blackdoc itself has failed in CI (not the files it was checking). Strange.

Waiting for #2806 to merge so I can proceed with tests.

A friendly ping that #2806 has been merged 🙂

Assigned @himkt although the work is still ongoing.

And, thanks a lot for the great work! At a quick glance, looks like a definite improvement. I'm just curious how critical Numba is to this functionality. Does the visualization become unusable without the JIT compilation (i.e. how much faster does it become with Numba)? We want to be careful introducing additional install requirements.

@hvy thank you for the question! Let me share a small bench test i did while developing this.

I understand your point about introducing additional install requirements though. As an alternative, i can move jitted code to separate module, try_import it, and fallback to default griddata solution if we are missing dependencies. This would move numba out of install requirements back to optional. Then i could add a note in dosctring of plot_contour informing users about this functionality. I'm just worried that many users would then see default at first go (although popular environments such as google colab or kaggle notebooks are including Numba by default). Please let me know what do you think of this solution.

Thanks for the numbers! With a separate module, do you mean independent of Optuna or within the Optuna library?

Interesting that Plotly is significantly faster than the Python implementation without the JIT compilation. I haven't taken a deeper look at the algorithm yet, but I'm curious whether there is room for optimizing the Python implementation without relying on Numba (e.g. by simple vectorization). If there is, we could perhaps leave it as future work and introduce this algorithm as the default one (given that the matplotlib visualizations are all still experimental). If not, try_import might be an option. But it'll complicate the behavior (and/or the API) so I'd like to hear inputs from others if possible.

@nzw0301 let me assign you as the author of the issue. Let me know if you're busy and I can reassign someone else. Do you have any thoughts or inputs on how to continue forward with this?

@hvy, sorry for not being very clear on that one. I meant module within Optuna, more specifically within optuna.visualization.matplotlib with imports working in the similar way to _matplotlib_imports.py.

I think Plotly speed comes from the fact that there is not much heavy lifting done python side. From what i know, execution is passed almost immediately to one of renderers.

I'm not sure if vectorization is feasible in this instance, since algorithm relies on very specific order in which missing values are interpolated (i. e. when imputing v[1] with mean of neighbors, there might be a case when its necessary to fill v[0] first, when those values are close to each other on the grid). There are two ways I think this algorithm could be speed up if we were to drop Numba:

• Interpolate z-matrix first, upsample to smooth contours later (currently its done other way around) - this would mean we are iterating over smaller matrices, in most cases at least. (and looking at it again, this is I think what Plotly does)
• Instead extensively using array indexing/slicing, base this algorithm on hashmap of coordinates, and iterate those. (and just build z-matrix out of it as the very last step)

I will explore both possibilities, before marking this as ready to review.

@hvy, so I've managed to cut no-JIT time from 1m 17s to 4.5s (on Intel Core i5) just by using hashmaps. This comes with no downsides to the quality of the plot and does not use any new dependencies. It's still a bit slower than Plotly or jitted numpy, but I think we are within reasonable runtime for a function that produces a plot. I don't think there is much to gain anymore with pure python or without diverging from Plotly algorithm. Overall im happy to exclude Numba and switch to the new approach, so please let me know if this is the level of performance we are ok with.

That sounds great!
Could you push the change (or create a separate PR if you like), and we could take a look at the implementation? I'm a bit curious about the time complexity how it scales, but it in any case sounds like a significant improvement that we should continue with.

hi, @xadrianzetx, sorry for the delayed response. We have had national holidays since last Thursday.

I'll take a look your this PR soon. Please give me a little bit more time.

best regards,

Thank you for the comments @nzw0301! Just FYI, it might be couple days before I'm able to address them, due to some hardware failures I'm currently resolving. Sorry for any delays!

No worries! It is totally fine. I hope your hardware issue is resolved🤞🏻

hi, let me give additional comments.

Personally using complex numbers looks cool! However, it is slightly hard for other committers to maintain the codes. So could you replace complex numbers with tuples or np.ndarray of two integers if the implementation does not make the computing performance severely worse? Related to this, zmap can be replaced with np.ndarray whose values are initialised at np.nan like np.full((len(xi), len(yi)), np.NaN) in _create_zmap.

In this complex number-free implementation, one drawback is that we need to care the boundary access with NEIGHBOR_OFFSETS in _find_coordinates_where_empty and _run_iteration, like np.maximum(np.minimum(coord + offset, contour_point_num-1), 0).

What do you think about it?

@nzw0301,

zmap can be replaced with np.ndarray whose values are initialised at np.nan like np.full((len(xi), len(yi)), np.NaN) in _create_zmap.

That was the design of initial version introduced in a27cdf4 and f7b343f. Unfortunately, without JIT, performance really suffered due to iterative nature of this algorithm, and Numpy element access being somewhat slow. Without Numba, we needed a data structure that offers fast access to its elements, preferably included in Python standard library, hence usage of hashmap.

So could you replace complex numbers with tuples or np.ndarray of two integers if the implementation does not make the computing performance severely worse?

The reason behind coordinates being expressed as complex numbers is, that it offers the fastest way to calculate locations of neighbors, with just one simple add to cover both x offset and y offset simultaneously. This is one of the most critical parts of the algorithm, which, assuming 200 Optuna trials, gets hit 9800 missing values * 100 optim iterations * 4 neighbors (excluding nan discovery part). I did a quick benchmark for both tuples and Numpy arrays (just the core part of addition operation looped over 3 milion iterations) and saw:

• tuple of coordinates (defined as tuple(sum(c) for c in zip(coord, offset))) being ~2x slower than complex
• Numpy arrays (defined as coord_arr + offset_arr) being ~1.4x slower than complex

Given those, I would be in favor of staying with current implementation. I do agree with you on maintainability point though, this algorithm is not the easiest thing to understand. To help with this, I think additional comments explaining grid system and algorithm steps could be introduced.

Thanks for reviews @nzw0301, @himkt! I've addressed all points in 34a887e, and added some additional comments in b830410.

@xadrianzetx

Thank you so much for the revise! Basically LGTM. ⭐
I have one question.

There still be little bit difference between plotly's plot and matplotlib's plot.
Do you know the cause of this difference?

Plotly	matplotlib

• matplotlib: https://67626-122299416-gh.circle-artifacts.com/0/docs/build/html/reference/visualization/generated/optuna.visualization.matplotlib.plot_contour.html#optuna.visualization.matplotlib.plot_contour
• plotly: https://67626-122299416-gh.circle-artifacts.com/0/docs/build/html/reference/visualization/generated/optuna.visualization.plot_contour.html#optuna.visualization.plot_contour

@himkt,

It might be due to the fact that for Plotly contour we are not doing any upsampling to trial params, so in your case matrix of shape 30x30 (roughly :)) is interpolated and contour smoothing is used, while in matplotlib implementation we are always resampling to 100x100 either with linspace or logspace. This could result in differences we see, especially for small number of trials.

Other than that, there might be slight differences in implementation between Plotly and matplotlib as far as calculating number and position of contours (looking at your example, matplotlib seems to be more detailed even though we are not specifying number of contour lines to use anywhere). To my best knowledge they both use marching squares, but I did not look up specific implementations.

It might be due to the fact that for Plotly contour we are not doing any upsampling to trial params, so in your case matrix of shape 30x30 (roughly :)) is interpolated and contour smoothing is used, while in matplotlib implementation we are always resampling to 100x100 either with linspace or logspace.

It makes sense. I agree with you that it results the difference. And I also think it is not bad point. 👍