dblalock / bolt Goto Github PK

I just want to use C++ code. So I cmake directly in the cpp directory。 Then run ./bolt，and it report a segment fault

At present, Bolt is only implemented for x86 machines with AVX2 instructions.

Convnet1M - 1 million convnet image descriptors
https://github.com/una-dinosauria/stacked-quantizers provide google driver links for Convnet1M
https://drive.google.com/file/d/0BxWzojlLp259aUt4Z1ZCMzVDQlk/view?usp=sharing
This url is no longer available.
Would you mind providing a valid link to download this dataset so that I can reproduce your experiments.Thank you!

Because it's 2017 and I should really have support for this. Should be very little work since the Python footprint is pretty small. We might support this already, in fact.

Hi, is there a set of public python code for your paper MADNESS ?

I see that lut_work_const can take the value of 2, 4, -1 (which seems to mean \infty). Does this make a difference to accuracy, and if so, which was the final version that I should use?

swigging python/bolt/native.i to python/bolt/native_wrap.cpp
swig -python -c++ -o python/bolt/native_wrap.cpp python/bolt/native.i
python/bolt/config.i:51: Error: Syntax error in input(1).
error: command 'swig' failed with exit status 1

OS: centos linux , python 3.7

OS: MacOS Monterey 12.5 (Intel chip)
Python: 3.10.5

❯ pytest tests
============================================================================== test session starts ===============================================================================
platform darwin -- Python 3.10.5, pytest-7.1.2, pluggy-1.0.0
rootdir: /Users/xiao/development/github.com/XiaoConstantine/bolt-1
collected 4 items

tests/test_encoder.py ..F.                                                                                                                                                 [100%]

==================================================================================== FAILURES ====================================================================================
________________________________________________________________________________ test_unquantize _________________________________________________________________________________

    def test_unquantize():
        X, Q = _load_digits_X_Q(nqueries=20)
>       enc = bolt.Encoder('dot', accuracy='high').fit(X)

tests/test_encoder.py:151:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
../../dblalock/bolt/venv/lib/python3.10/site-packages/pybolt-0.1.4-py3.10-macosx-11-x86_64.egg/bolt/bolt_api.py:466: in fit
    centroids = _learn_centroids(X, ncentroids=ncentroids,
../../dblalock/bolt/venv/lib/python3.10/site-packages/pybolt-0.1.4-py3.10-macosx-11-x86_64.egg/bolt/bolt_api.py:142: in _learn_centroids
    centroids, labels = kmeans(X_in, ncentroids)
../../dblalock/bolt/venv/lib/python3.10/site-packages/pybolt-0.1.4-py3.10-macosx-11-x86_64.egg/bolt/bolt_api.py:106: in kmeans
    seeds = kmc2.kmc2(X, k).astype(np.float32)
kmc2.pyx:97: in kmc2.kmc2
    ???
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

>   ???
E   ValueError: probabilities contain NaN

mtrand.pyx:935: ValueError

I'm sorry but I don't quite understand this line.

Let's say we have ncols_out_per_group=4, then we have

    out_ptrs[0] = codes_out + (col_out_1 * 32)
    out_ptrs[1] = codes_out + (col_out_2 * 32)
    out_ptrs[2] = codes_out + (col_out_3 * 32)
    out_ptrs[3] = codes_out + (col_out_4 * 32)

where col_out_2 = col_out_1 + 1, col_out_3 = col_out_2 + , and col_out_4 = col_out_3 + 1.

Then, when we're done with one block, as in

out_ptrs[gg] is increased by 32 * ncolgroups. If we have, say, ncolgroups=2, then out_ptrs[0] would equal to out_ptrs[2], and out_ptrs[1] would equal to out_ptrs[3].

If I was mistaken could you please point it out. Would be best if you could tell me the layout of the zipped output.

Thanks a lot!

Summary

The avx sgemm test fails at n=14 on my system, apparently due to a general protection fault reading unaligned memory.

Problem Information

_mm256_load_ps raises a general protection fault if an address is passed to it that is not aligned to 32 bytes.
Documentation: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm256_load_ps&ig_expand=4279

System information

$ cat .git/refs/heads/master
e7726a4c165cc45ac117e9eabd8761013a26640e
$ uname -a
Linux DESKTOP-E3P7TC0 3.10.0-1160.62.1.el7.x86_64 #1 SMP Wed Mar 23 09:04:02 UTC 2022 x86_64 GNU/Linux
$ cat /etc/system-release
Red Hat Enterprise Linux Workstation release 7.9 (Maipo)

Diagnostic Information

$ gdb cpp/bolt-build/bolt
(gdb) run
Starting program: /shared/src/bolt/cpp/bolt-build/bolt 
brute force sgemm test, n = 1...
brute force sgemm test, n = 2...
brute force sgemm test, n = 5...
brute force sgemm test, n = 14...

Program received signal SIGSEGV, Segmentation fault.
0x00000000005a1af9 in _mm256_load_ps (__P=0x886cf8) at /usr/local/lib/gcc/x86_64-pc-linux-gnu/9.4.1/include/avxintrin.h:874
874       return *(__m256 *)__P;
(gdb) up
#1  (anonymous namespace)::sgemm_colmajor_narrow_padded<1, 2> (A=0x8878e0, B=0x875d80, N=14, D=1, M=2, out=0x886cc0, add_to_output=false, A_col_stride=14, B_col_stride=1, 
    out_col_stride=14, nrows_per_chunk=512) at /home/user/src/bolt/cpp/src/utils/avx_utils.hpp:394
394                             sums[mm] = _mm256_load_ps(out_ptr);
(gdb) p out_ptr
$1 = (float *) 0x886cf8
(gdb) bt
#0  0x00000000005a1af9 in _mm256_load_ps (__P=0x886cf8) at /usr/local/lib/gcc/x86_64-pc-linux-gnu/9.4.1/include/avxintrin.h:874
#1  (anonymous namespace)::sgemm_colmajor_narrow_padded<1, 2> (A=0x8878e0, B=0x875d80, N=14, D=1, M=2, out=0x886cc0, add_to_output=false, A_col_stride=14, B_col_stride=1, 
    out_col_stride=14, nrows_per_chunk=512) at /home/user/src/bolt/cpp/src/utils/avx_utils.hpp:394
#2  0x000000000059ff9e in sgemm_colmajor (A=0x8878e0, B=0x875d80, N=14, D=1, M=2, out=0x886cc0) at /home/user/src/bolt/cpp/src/utils/avx_utils.cpp:18
#3  0x00000000005ee949 in _test_sgemm_colmajor<-1, -1> (N=14, D=1, M=2, simple_entries=false) at /home/user/src/bolt/cpp/test/test_avx_utils.cpp:54
#4  0x00000000005ec3f5 in ____C_A_T_C_H____T_E_S_T____100 () at /home/user/src/bolt/cpp/test/test_avx_utils.cpp:155
#5  0x00000000005bb56e in Catch::FreeFunctionTestCase::invoke (this=0x86ef90) at /home/user/src/bolt/cpp/test/external/catch.hpp:5507
#6  0x00000000005aa337 in Catch::TestCase::invoke (this=0x889280) at /home/user/src/bolt/cpp/test/external/catch.hpp:6389
#7  0x00000000005b972b in Catch::RunContext::runCurrentTest (this=0x7fffffffd560, redirectedCout="", redirectedCerr="") at /home/user/src/bolt/cpp/test/external/catch.hpp:5131
#8  0x00000000005b8737 in Catch::RunContext::runTest (this=0x7fffffffd560, testCase=...) at /home/user/src/bolt/cpp/test/external/catch.hpp:5001
#9  0x00000000005ba095 in Catch::Runner::runTests (this=0x7fffffffd810) at /home/user/src/bolt/cpp/test/external/catch.hpp:5275
#10 0x00000000005bae1b in Catch::Session::run (this=0x7fffffffdb10) at /home/user/src/bolt/cpp/test/external/catch.hpp:5395
#11 0x00000000005bace8 in Catch::Session::run (this=0x7fffffffdb10, argc=1, argv=0x7fffffffdce8) at /home/user/src/bolt/cpp/test/external/catch.hpp:5378
#12 0x00000000005ae8bb in main (argc=1, argv=0x7fffffffdce8) at /home/user/src/bolt/cpp/test/main.cpp:22

$ valgrind cpp/bolt-build/bolt
==5087== Memcheck, a memory error detector                                                     
==5087== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.                       
==5087== Using Valgrind-3.18.0.GIT and LibVEX; rerun with -h for copyright info                
==5087== Command: cpp/bolt-build/bolt                                                          
==5087==                                                                                       
brute force sgemm test, n = 1...                                                               
brute force sgemm test, n = 2...                                                               
brute force sgemm test, n = 5...                                                                                                                                                              
brute force sgemm test, n = 14...                                                                                                                                                             
==5087==                                                                                                                                                                                      
==5087== Process terminating with default action of signal 11 (SIGSEGV)                                                                                                                       
==5087==  General Protection Fault                                                                                                                                                            
==5087==    at 0x5A1AF9: _mm256_load_ps (avxintrin.h:874)                                                                                                                                     
==5087==    by 0x5A1AF9: void (anonymous namespace)::sgemm_colmajor_narrow_padded<1, 2>(float const*, float const*, int, int, int, float*, bool, int, int, int, int) (avx_utils.hpp:394)      
==5087==    by 0x59FF9D: sgemm_colmajor(float const*, float const*, int, int, int, float*) (avx_utils.cpp:18)                                                                                 
==5087==    by 0x5EE948: void _test_sgemm_colmajor<-1, -1>(int, int, int, bool) (test_avx_utils.cpp:54)                                                                                       
==5087==    by 0x5EC3F4: ____C_A_T_C_H____T_E_S_T____100() (test_avx_utils.cpp:155)                                                                                                           
==5087==    by 0x5BB56D: Catch::FreeFunctionTestCase::invoke() const (catch.hpp:5507)                                                                                                         
==5087==    by 0x5AA336: Catch::TestCase::invoke() const (catch.hpp:6389)                                                                                                                     
==5087==    by 0x5B972A: Catch::RunContext::runCurrentTest(std::string&, std::string&) (catch.hpp:5131)
==5087==    by 0x5B8736: Catch::RunContext::runTest(Catch::TestCase const&) (catch.hpp:5001)
==5087==    by 0x5BA094: Catch::Runner::runTests() (catch.hpp:5275)
==5087==    by 0x5BAE1A: Catch::Session::run() (catch.hpp:5395)
==5087==    by 0x5BACE7: Catch::Session::run(int, char* const*) (catch.hpp:5378)
==5087==    by 0x5AE8BA: main (main.cpp:22)

Work to Resolve

I pursued this just a little bit before changing tasks. Following the control flow, it looked to me like the unaligned memory arose from passing a matrix with a nonaligned stride greater than 8, to sgemm_colmajor. I've come up with the below so far, but have not yet tested and debugged it and make frequent mistakes so likely something is wrong. The patch is pasted here from a tmux pane and then hand edited, so may need manual application.

diff --git a/cpp/test/test_avx_utils.cpp b/cpp/test/test_avx_utils.cpp
index 4ec4e00..34c318a 100644
--- a/cpp/test/test_avx_utils.cpp
+++ b/cpp/test/test_avx_utils.cpp
@@ -44,6 +44,8 @@ void _test_sgemm_colmajor(int N, int D, int M, bool simple_entries=false) {
         B.setRandom();
     }
     C = (C.array() + -999).matrix();  // value we won't accidentally get
+    int aligned_rows = C.rows() - (C.rows() % (-32 / int(sizeof(float))));
+    C.resize(aligned_rows, C.cols());

At present, Bolt's python code doesn't appear to be building on Ubuntu and hasn't been tested on Windows. It may also have issues building on other systems.

Dear Experts:

     Greetings!
     When I tried to run C++ code of Bolt on my own computer, I faced an issue: "undeclared inclusion(s) in rule '//:mithral'". Could you please shed some lights or clues with me?

Thank you so much. 🙏

Part of log file:

[root@cdh-hadoop cpp]# bazel build :main
INFO: Analyzed target //:main (14 packages loaded, 4445 targets configured).
INFO: Found 1 target...
ERROR: /root/bolt/cpp/BUILD:17:11: undeclared inclusion(s) in rule '//:mithral':
this rule is missing dependency declarations for the following files included by 'src/quantize/mithral.cpp':
'/usr/local/gcc/lib/gcc/x86_64-unknown-linux-gnu/5.2.0/include/stdint.h'
'/usr/local/gcc/lib/gcc/x86_64-unknown-linux-gnu/5.2.0/include/stddef.h'

......
......

INFO: Elapsed time: 16.148s, Critical Path: 7.51s
INFO: 0 processes.
FAILED: Build did NOT complete successfully

Hi, I would like to use the library just to to compress/uncompress large numpy arrays in order to send them faster through the network.
Can it be done?

ThanksQ

I want to run this repo's program via Python , but an error occurred on my Ubuntu18.04 like following. Can I get your opinion please?

'''
swigging cpp/src/external/eigen/.hg/......
swig -python -c++ -o cpp/src/extenal/eigne/.hg/......Error: Unterminated string constant
error: command 'swig' failed with exit status 1
'''

Does the mithral C++ codebase provide functions for parameter optimization? I have problems finding it and executing run_matmul() in the struct mithral_amm_task returns a wrong output matrix, since the optimization parameters are set randomly. Thank you!

Hello,

I've seen the other thread about installation but did not find an answer to my problem.

I can install swig and numpy but when I do python3 setup.py install I get the following

....
running install
running bdist_egg
running egg_info
writing pybolt.egg-info/PKG-INFO
writing dependency_links to pybolt.egg-info/dependency_links.txt
writing requirements to pybolt.egg-info/requires.txt
writing top-level names to pybolt.egg-info/top_level.txt
reading manifest file 'pybolt.egg-info/SOURCES.txt'
writing manifest file 'pybolt.egg-info/SOURCES.txt'
installing library code to build/bdist.macosx-10.9-x86_64/egg
running install_lib
running build_py
creating build/lib.macosx-10.9-x86_64-3.7
creating build/lib.macosx-10.9-x86_64-3.7/bolt
copying python/bolt/bolt.py -> build/lib.macosx-10.9-x86_64-3.7/bolt
copying python/bolt/bolt_api.py -> build/lib.macosx-10.9-x86_64-3.7/bolt
copying python/bolt/__init__.py -> build/lib.macosx-10.9-x86_64-3.7/bolt
copying python/bolt/native.i -> build/lib.macosx-10.9-x86_64-3.7/bolt
running build_ext
building '_bolt' extension
swigging python/bolt/native.i to python/bolt/native_wrap.c
swig -python -o python/bolt/native_wrap.c python/bolt/native.i
python/bolt/config.i:50: Warning 301: class keyword used, but not in C++ mode.
python/bolt/config.i:51: Error: Syntax error - possibly a missing semicolon.
error: command 'swig' failed with exit status 1

It seems swig is not installed but I can do swig -version and I get

SWIG Version 4.0.2

Compiled with clang++ [x86_64-apple-darwin21.1.0]

Configured options: +pcre

Please see http://www.swig.org for reporting bugs and further information

swig has been installed successfully.
After entering python setup.py install, following messages show up

/opt/homebrew/lib/python3.9/site-packages/setuptools/dist.py:642: UserWarning: Usage of dash-separated 'description-file' will not be supported in future versions. Please use the underscore name 'description_file' instead
warnings.warn(

building '_bolt' extension
swigging cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i to cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake_wrap.cpp
swig -python -c++ -o cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake_wrap.cpp cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i
cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i:3: Error: Unterminated string constant
error: command '/opt/homebrew/bin/swig' failed with exit code 1

python/bolt/config.i:47: Warning 315: Nothing known about 'Eigen::RowMajor'.
swigging cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i to cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp
swig -python -c++ -o cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Illegal token '�'.
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Syntax error in input(1).
error: command 'swig' failed with exit status 1

OS: ubuntu16.04, python version:anaconda python 3.8

When learning the clusters for MithralEncoder, at this line I ran into the following issue:

AttributeError: module 'sklearn.linear_model' has no attribute 'ridge'

Upon inspection, it seems that perhaps modifying the line to replace .ridge.Ridge with either .Ridge or ._ridge.Ridge may fix the issue. Is it possible there is an sklearn version mismatch with my installation?

OS: macOS Big Sur 11.5.2
Python: 2.7.17

Follow the steps mentioned in README, brew install swig, then numpy, last setup install

Still getting following error:

swigging cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i to cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp
swig -python -c++ -o cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Illegal token '�'.
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Syntax error in input(1).
error: command 'swig' failed with exit status 1

Any idea what's going on here? I m not familiar with this swig thing

I need to run MADDNESS Python implementation algorithm. My python version is py3.7 and there is a dependency Kmc2 which is compatible with Python 2.7. I want to ask for a suggestion about how to build the environment, because Python version 2.7 does not support matrix multiplication operators and 'F' prefix.

I opened an issue for this, but the issue appears to have been deleted without comment somehow. I put a lot of work into formatting it to help anybody else engage it.

The default bolt testsuite is triggering a general protection fault in old code, apparently due to accessing memory from larger matrices with strides that are not a multiple of 32 bytes, at unaligned offsets.

I made a little progress on this, but an organised form of my change was only held in the lost issue.

I'll store a local copy of this issue, and update it to work it better.

Could you please share your experiment data in the script (matmul_datasets.py)? You may upload the following *.npy files and give me a link, I can download them myself.

These data types are much more useful in the science caculation. I would like to modify the data type but worry the algorithm cannot support that.

Python version: 3.8.11
Swig version: 3.0.12
OS: Ubuntu 20.04.3 LTS
Error information:

swigging cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i to cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake_wrap.cpp
swig -python -c++ -o cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake_wrap.cpp cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i
cpp/src/external/eigen/.hg/store/data/_c_test_config.cmake.i:3: Error: Unterminated string constant
error: command 'swig' failed with exit status 1

My system is Win10
SWIG Version 3.0.12

Using something like the eve library could work well to allow writing code that works on different architectures. I'm specifically interested in an SSE4.1 or AVX implementation.

I could probably look into working on this sometime next month if I have time.

I couldn't find any c++ examples (including basic matrix multiply) here. Any related code snippet would be very helpful... 😢

I was unable to get BOLT working on python three after a bit of debugging.

I finally tried pip installing it, and see an error message stating only python 2.6+ is supported.

Is there any way to get python 3 supported?

python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:47: Warning 315: Nothing known about 'Eigen::RowMajor'.
python/bolt/config.i:45: Warning 315: Nothing known about 'Eigen::Matrix'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:47: Warning 315: Nothing known about 'Eigen::RowMajor'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:47: Warning 315: Nothing known about 'Eigen::RowMajor'.
python/bolt/config.i:45: Warning 315: Nothing known about 'Eigen::Matrix'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:46: Warning 315: Nothing known about 'Eigen::Dynamic'.
python/bolt/config.i:47: Warning 315: Nothing known about 'Eigen::RowMajor'.
swigging cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i to cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp
swig -python -c++ -o cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in_wrap.cpp cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Illegal token '�'.
cpp/src/external/eigen/.hg/store/data/_c_test_custom.cmake.in.i:1: Error: Syntax error in input(1).
error: command 'swig' failed with exit status 1

At present, Bolt is only implemented for x86 machines with AVX2 instructions. Adding support for other architectures would entail reimplementing the code in bolt.hpp and adding #ifdefs to select the appropriate implementation for the target architecture.

Or to other traditional matrix workloads?

(You know, the folks we originally thought we were introducing vector processing for...)

error: invalid path 'experiments/results/correlation_dotprods/_LabelMe/all_results?.csv'

Hello, I‘m beginner，want to run this program in C++，install BAZEL according to your instructions，and bazel run :main，the above was successful，I would like to ask if you have a complete test code for C++，just like：Input two matrices and output a multiplication result。Additional question，bazel run :main finish，What is the result of bazel run :main？ Is Bolt's library function API？