CRAN submission!

[LTLA]

I'm also looking forward to a CRAN submission for this package; it'll allow me to give Annoy some company in the "approximate NN methods" section of BiocNeighbors. It looks pretty ready to go - is there anything else that needs to be done?

Also, insofar as you're using C++11, you could replace &dv[0] with dv.data().

[jlmelville]

The package is in a reasonable state, although I've not put it through its paces as much as I should. Also, there's some RcppParallel stuff in there that might not work right and might need to just be removed.

The Python wrappers allow for searching by label, which I haven't implemented. Not sure how much demand there is for that.

Apart from that, this could be submitted to CRAN, if you think it adds some value over Annoy. I haven't done much benchmarking to see if the difference is large once you no longer have access to platform-specific code.

And thank you for the micro code-review!

[LTLA]

I'm not too worried about the AVX stuff. In fact, for Annoy, I explicitly turned off the vectorization to avoid debugging headaches due to platform-to-platform differences in compilation. (As you now, vectorization performs additions in a different order, so the distances would be slightly different due to round-off error at each addition - a fact that is probably more pronounced when using float.)

Annoy's plenty fast without vectorization, and I imagine that I would reach the same conclusion for HNSW. I don't know what the head-to-head is like, though - if these graphs are to be believed, HNSW dominates Annoy in all tested data sets, though this probably depends on the data.

[LTLA]

Putting my money where my mouth is: https://github.com/LTLA/BiocNeighbors/tree/hnsw.

[jlmelville]

@LTLA, once again thank you for the pull requests.

Before proceeding with CRAN submission, I plan to spend some quality time with at least some of the HDF5 datasets that ann-benchmarks offer. This has already resulted in some extra refactoring. If there are no unpleasant surprises we are probably good to go.

[LTLA]

@jlmelville, I was wondering whether it would be a good idea to push your portability modifications upstream to the original hnswlib repo. I can't imagine we're the only people running into this. (Also, it would reduce divergence of your code from hnswlib, which would make it easier to update RcppHNSW when upstream changes occur.) Would @yurymalkov be willing to entertain a PR?

For full portability, I would guess that we would also need #ifdefs around the _mm_prefetch calls as well (or use some macro magic)... that doesn't look like standard C++ to me. And we should probably skip any attempt to #include intrinsics headers or to define PORTABLE_ALIGN32.

[jlmelville]

Yeah, I have toyed with the idea a few times, but didn't want to shift the maintenance burden upstream if no-one else was going to care. I should probably put it out there anyway.

If you have the time, would you mind pointing to line numbers that you think still need looking at?

[LTLA]

Went one better and made #3. I haven't run this through a build system yet, but I think I caught all of the non-standard C++ lying around. I don't think it would be particularly selfish of us to pass the changes upstream, a problem shared is a problem halved and all that.

[LTLA]

I noticed that the default ef in the R-exposed KNN function is set to ef_construction, while the HNSW library sets ef_=10. What's the motivation for the change? I'm fine with it either way, I was just curious whether you were getting noticeably better results with larger ef.

[jlmelville]

No reason other than when I realised I had failed to differentiate between ef and ef_construction I arbitrarily set the default for the newly introduced parameter. I've changed this to 10.

I have yet to come to any conclusions about parameter settings. I was able to run through four of the ann-benchmarks datasets without any problems, but it's a lot slower than Annoy (which seems counter to the benchmarks results). I assume this is because I am running this package via devtools, which uses much more conservative compiler settings, and not the switch to mtune=generic.

As the package has been through a lot of churn over the past couple of days I haven't got round to installing a non-dev version via remotes to do proper evaluation of speed versus accuracy. I'd be interested in any findings you have.

[jlmelville]

On the subject of pushing the preprocessor additions up to HNSW itself:

1. I already have a fork of nmslib/hnswlib that can be used for creating the PR. But you've now done more work on this than I have. Do you want to take over creating a PR (and the fame that is sure to follow)?
2. It now occurs to me to ask: will these changes require people using the current version of HNSW to change their compiler flags to get the old behavior, or does nothing change unless specifically asked for? I realise that this might mean going back to the preprocessor flags that begin with NO_ that I was iffy on back in Improve portability for non-x86 architectures #3.
3. Do you have a brief summary of the preprocessor flags that have been introduced and their meaning?

[LTLA]

1. I don't think that's necessary, you did most of the initial work anyway. (Unless you don't want to push it, in which case I'm happy to do it. It's possible that we missed something; I've only done cursory tests on the AVX-enabled version.)
2. I don't think so. The old behaviour was to use vectorization, which will continue to be the case provided that (i) users do not define NO_MANUAL_VECTORIZATION, and (ii) they have AVX and SSE support enabled . If (ii) does not hold, the modifications are in fact safer, as it will ensure that the compiler will still produce a valid binary for these architectures.
3. The main change is that of NO_MANUAL_VECTORIZATION, which if defined will turn off all uses of AVX and SSE for maximum portability across different architectures. Finer control is achievable with USE_AVX or USE_SSE, which if defined will use AVX and SSE instructions respectively. By default, the library will use AVX or SSE instructions if it detects they are supported.

[jlmelville]

Ok, I will deal with the PR. Thanks for the info. I will at least test a few combinations of the compiler flags before submitting upstream.

[jlmelville]

@LTLA, how are the USE_AVX and USE_SSE flags meant to be used? I have changed:

PKG_CXXFLAGS = -DNO_MANUAL_VECTORIZATION

to:

PKG_CXXFLAGS = -DUSE_AVX

and I get the warning:

   In file included from hnsw.cpp:29:0:
   ../inst/include/hnswlib.h:6:0: warning: "USE_AVX" redefined
    #define USE_AVX
    ^
   <command-line>:0:0: note: this is the location of the previous definition

[LTLA]

Both of these USE_* macros are intended to be internal (they represent the combination of the user-specified intention for vectorization and the availability of SSE/AVX support on the system). If you wanted, you could do something like -DNO_MANUAL_VECTORIZATION -DUSE_SSE, which will turn off automatic use of all vectorization but preserve use of SSE intrinsics. Same for USE_AVX.

However, I'm not sure how safe it is to set the USE_* macros directly. For starters, you'll force the compiler to generate SSE/AVX instructions for architectures that might not support it. I am also unsure that it makes sense to define USE_AVX without USE_SSE, as the AVX-only functions still use SSE intrinsics (explicitly in our source code, and perhaps implicitly as well).

[jlmelville]

Thanks for the clarification. I tried combining -DNO_MANUAL_VECTORIZATION -DUSE_SSE, but it gives a compiler error. But as long as it's understood that we only intend -DNO_MANUAL_VECTORIZATION to be used, that's fine. It also makes explaining the PR nice and simple.

[LTLA]

What compiler error did you get? I go through fine when I set NO_MANUAL_VECTORIZATION with USE_SSE. It fails with USE_AVX only but it probably doesn't make sense to ask for AVX without SSE anyway.

[jlmelville]

My mistake. I got the error with USE_AVX, but it's just an unused variable warning with USE_SSE.

[LTLA]

Might be a good idea to remove line 174 in space_ip.h to get rid of the unused variable.

[jlmelville]

PR has been submitted at: nmslib/hnswlib#85 -- Travis CI failed however in the python bindings test. Any ideas on that one?

[LTLA]

Looking at it now. I don't have much python binding experience, but let's see.

[LTLA]

Well, I would look at it, if I could get Python 3 to install... argh.

[LTLA]

Huh. python3 setup.py test works fine for me (MacOSX, Python 3.7.1, Clang 6.0).

[LTLA]

I think I know where this comes from. The statements in bindings_test_labels.py:

        self.assertAlmostEqual(diff_with_gt_labels,0,1e-4)

... are probably incorrect, as the third argument should be an integer according to this. This is consistent with the error message observed in the latest Travis build.

Now, the question is why this causes problems here and not in the master branch build. It seems that the third argument doesn't even come into play when the first two arguments are exactly equal. This seems to be the case on some systems (such as my mac) and sometimes not (such as Travis).

I'm not sure why the situation changed with the addition of our macros, but it seems that the arguments being tested are floats that weren't meant to be exactly equal anyway...

[jlmelville]

PR has been checked into nmslib/hnswlib master and I have synced back up. Onwards.

I should probably document how to use the package with the data provided by ann-benchmarks, but I don't know how useful it would be as a vignette as none of the code should be automatically run.

[LTLA]

Is it time to finish the fight? What else do we need - a vignette, perhaps? I can whip one up from your example in the README; and/or I could make one in the same vein as RcppAnnoy's vignette.

[jlmelville]

If you can think of a vignette that will be useful, go for it. I'm not a huge fan of vignettes which don't add much beyond simple examples, or where the code isn't being run because it takes too long (which would have happened with anything to do with ann-benchmarks) and my inspiration has run dry.

I am waiting on:

1. Whether gcc UBSan runtime error: load of misaligned address nmslib/hnswlib#87 will be fixed. Technically, it causes devtools::check_rhub() to fail.
2. I will be unavailable for "internet stuff" all of next week so I didn't want to submit while I was out of contact. Also, I assume there will be a bit of a backlog due to CRAN submission being closed over Christmas anyway, so I wasn't raring to add to the backlog.

[LTLA]

Okay. Not having a vignette is fine as well; I'm just used to it for BioC submissions.

Reading nmslib/hnswlib#87 reminds me how lucky I am to not have to mess around with pointer casts.

[jlmelville]

nmslib/hnswlib#87 is fixed. I will aim to submit sometime after the 14th January.

[LTLA]

Nudge. (Let me know if there's anything I can help with.)

[jlmelville]

I uploaded the submission to CRAN yesterday. Will update in the face of glorious victory/crushing defeat.

[jlmelville]

We're in: https://cran.r-project.org/package=RcppHNSW.

Thank you for your help @LTLA.

[LTLA]

Great work. Immediate rev-dep from BiocNeighbors as soon as it builds!

[LTLA]

Well, it's built, so you can see the spanking new dependency on the BiocNeighbors page. It's a shame that CRAN doesn't track BioC reverse dependencies on the RcppHNSW landing page, but whatever.

What's the story behind STRICT_R_HEADERS? I'm getting CHECK failures on Windows, did you get something similar before you added it? To be clear, I know what it does, I just want to know how you decided to add it.

[jlmelville]

It looks like STRICT_R_HEADERS is going to be turned on in Rcpp at some point this year (RcppCore/Rcpp#898), so I wanted to test there won't be any problems.

Where are the CHECK failures happening on Windows? I'm not seeing anything either locally or on the CI.

[LTLA]

Sorry, I was referring to CHECK failures on BiocNeighbors, related to the HNSW code:

http://bioconductor.org/checkResults/devel/bioc-LATEST/BiocNeighbors/tokay2-checksrc.html

Bit of a head-scratcher, as it's the same C++ code, yet RcppHNSW checks fine but BiocNeighbors falls apart. Maybe it's something to do with the lack of RcppHNSW Windows binaries from CRAN.

[LTLA]

RcppHNSW binaries just got released on CRAN - let's see how the next BioC build goes for BIocNeighbors. I was hoping you'd say something like "oh yeah, RcppHNSW didn't compile on Windows until I added STRICT_R_HEADERS" but that doesn't seem to be the case.

Sigh - another round of head-banging-on-wall action to debug the Windows build... it's not the first time, and it probably won't be the last.

[LTLA]

Gah! Turned out to be a memory overrun on my end. Whoops.

The other test failure seems to be due to some differences between R's sqrt and std::sqrt on Win64. 🤷‍♂️

But this is all fixed now, and the panel is all green:

http://bioconductor.org/checkResults/devel/bioc-LATEST/BiocNeighbors

... so let the party begin!