falconn-lib / ffht Goto Github PK

Hi,
I don't know what I am doing, so sorry if the issue is stupid.
When I import ffht, I get an import error
ImportError: [...]/anaconda3/lib/python3.6/site-packages/FFHT-1.1-py3.6-linux-x86_64.egg/_ffht.cpython-36m-x86_64-linux-gnu.so: undefined symbol: fast_copy

For installation, I did
cd FFHT-master/
../anaconda3/bin/python setup.py install

Thank you.

If you apply a predetermined random pattern of sign flipping to an input array followed by the fast (Walsh) Hadamard transform you get a random projection of the input data. You can use that for unbiased dimension reduction or increase. Repeat the process for better quality.
The outputs of the random projection strongly follow the Gaussian distribution because the central limit theorem applies not only to sums but also sums and differences.
Anyway if you binarize the outputs of the the random projection you have a locality sensitive hash. If you interpret the output bits as +1,-1 you can multiply each bit by a weight and sum to get a recalled value. To train, recall and calculate the error. Divide by the number of bits. Then add or subtract that from each weight as appropriate to make the error zero. In that way you have created an associative memory.
Because the error has been distributed non-similar input will result in the error fragments being multiplied by arbitrary +1,-1 hash bit values. Again you can invoke the central limit theorem to see the error fragments sum to zero mean, low level Gaussian noise.
The memory capacity is just short of the number of bits. If you use the system under capacity you get some repetition code error correction.
Basically when you store an new memory in that system all the previous memories get contaminate by a little bit of Gaussian noise. However for an under capacity set of training data you can drive that noise to zero by repeated presentation.
This also provides a means to understand extreme learning machines and reservoir computing as associative memory.

I have this legacy SSE code which I have been using for a number of years:
https://drive.google.com/open?id=1bhQi4BybXPkvCENIYQcdw9PHAwS9Ocam
I get about 5000 65536-point WHT's per second per core on an Intel Celeron in a cheap laptop. I think your code on say a modern AMD 32 core processor can match a GPU. Unless there was some way to use the GPU tensor cores efficiently for the WHT.
There are many applications for the WHT that are not well known:
https://github.com/S6Regen

For instance, when the chunk size is too small and FFHT returns -1, it would be nice to print the reason for the negative return code to STDERR.

We need to ask Berkeley people to contribute their Scala/Java wrapper for humanity.

Do you have any intention or interest in providing an out-of-place FHT? Many applications, such as Orthogonal JL Transform and random orthogonal embedding kernel methods, would benefit from having distinct input and output locations.

Unresolved symbol errors occur when using gcc7 or 6 but succeeds with gcc4.

See http://clang.llvm.org/compatibility.html#inline for an explanation. A fix is simply replacing "inline" with "static inline", which I can confirm works with gcc7 and clang.

Example error:

Undefined symbols for architecture x86_64:
  "_helper_double_10", referenced from:
      _fht_double in fht.o
  "_helper_double_11", referenced from:
      _fht_double in fht.o
  "_helper_double_5", referenced from:
      _fht_double in fht.o
  "_helper_double_6", referenced from:
      _fht_double in fht.o
  "_helper_double_7", referenced from:
      _fht_double in fht.o
  "_helper_double_8", referenced from:
      _fht_double in fht.o
  "_helper_double_9", referenced from:
      _fht_double in fht.o
  "_helper_float_12", referenced from:
      _fht_float in fht.o
  "_helper_float_4", referenced from:
      _fht_float in fht.o
  "_helper_float_5", referenced from:
      _fht_float in fht.o
  "_helper_float_6", referenced from:
      _fht_float in fht.o
  "_helper_float_9", referenced from:
      _fht_float in fht.o
ld: symbol(s) not found for architecture x86_64

This is fixed in my fork, but it also adds some additional methods which might not be worthy of inclusion and a simple replacement of 'inline' with 'static inline' might be preferable.

Hi, when the length of buf is odd are you using a deepcopy and a zero-padding on the input data buf of fht_double(buf, log_n)? In this case, log_n has to be the next or previous binary logarithm?

In larger programs, a SIGSEGV can be hard to trace back to FFHT.

I want to reduce Hadamard Transform every column in my matrix.
Is there currently a way to do this with FFHT without using a python outer loop?

I met an error when installing the package on my Mac. And I don't know whether this error is common and I'm quite confused about how to deal with it. Thank you very much!

/core/include/numpy/ndarraytypes.h:1816:
/Users/zhanght/anaconda3/lib/python3.6/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: 
      #warning is a language extension [-Wpedantic]
#warning "Using deprecated NumPy API, disable it by " \
 ^
/Users/zhanght/anaconda3/lib/python3.6/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: 
      "Using deprecated NumPy API, disable it by "          "#defining
      NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-W#warnings]
_ffht.c:52:17: warning: implicit declaration of function 'Py_InitModule3' is
      invalid in C99 [-Wimplicit-function-declaration]
  PyObject *m = Py_InitModule3("_ffht", module_methods, module_docstring);
                ^
_ffht.c:52:17: warning: this function declaration is not a prototype
      [-Wstrict-prototypes]
_ffht.c:52:13: warning: incompatible integer to pointer conversion initializing
      'PyObject *' (aka 'struct _object *') with an expression of type 'int'
      [-Wint-conversion]
  PyObject *m = Py_InitModule3("_ffht", module_methods, module_docstring);
            ^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
_ffht.c:53:11: error: non-void function 'init_ffht' should return a value
      [-Wreturn-type]

When I run make in the measurements directory, there is no "to_run.h" file. Is this the right way to run the benchmark?

I assume FFHT doesn't have OpenMP support? If so, do you see any reason why it cannot/should not have?

My guess is that under the hood there are loops which can be sped up even more. Can someone help me out by pointing out where the innermost loops of the ffht implementation are located (my guess is that they are in fht_avx.c)?

Thanks!

Hi,
I am trying to use FFHT for one of my projects, as it is the fastest library for this purpose. I tried installing it with initially no success. I don't code much in C, and am not particularly familiar with the Python-C API, but after a day of googling I identified the following issues with the Python wrapper:

• Py_InitModule3 seems to be deprecated and one should be using a combination of PyModuleDef and PyModule_Create instead. Okay, I rewrote the relevant parts of the _ffht.c file, and it installs seemingly fine, but
• it seems like there is no return value implemented as the _ffht.c file ends with return Py_BuildValue("");

Again, I'm not really sure whether I am doing something wrong, or the second one is actually an issue. Any help is appreciated

I'm excited to find such a good implementation, but I'm curious to know what to do when the dimension of my data is not a power of two

I have a workaround but don't know how to get it to work in a way that doesn't interfere with builds on Linux. This serves to document what I've found.

I tried running setup.py on Windows with a default python 2.7.15 install from the python website and got a notice to install some MSVC for python:

https://www.microsoft.com/en-us/download/details.aspx?id=44266

Running setup.py with that installed gave me another error that MS compiler cl.exe doesn't understand the "-Wextra" option. So, I thought I'd try mingw-w64, which I already have installed in my system since it definitely understands -Wextra, being vanilla gcc. I followed the official python steps (https://wiki.python.org/moin/WindowsCompilers) to configure it to use that as the compiler.

After that, running setup.py with mingw-w64's gcc as the compiler gave the error:
undefined reference to `__imp_Py_InitModule4'

Finally googling that turned up that adding -DMS_WIN64 as a compiler option works, so I did that:

diff --git a/setup.py b/setup.py
index 223aa70..01835bc 100644
--- a/setup.py
+++ b/setup.py
@@ -26,7 +26,7 @@ module = Extension('_ffht',
                    extra_compile_args=['-march=native', '-O3', '-Wall', '-Wextra', '-pedantic',
                                        '-Wshadow', '-Wpointer-arith', '-Wcast-qual',
                                        '-Wstrict-prototypes', '-Wmissing-prototypes',
-                                       '-std=c99', '-DFHT_HEADER_ONLY'],
+                                       '-std=c99', '-DFHT_HEADER_ONLY', '-DMS_WIN64'],
                    include_dirs=[np.get_include()])

 setup(name='FFHT',

Hope this helps others using this FFHT on windows. I don't want to maintain the setup.py script to be Windows compatible, but I hope others can use these tips to help them, or someone will come along and add some checks to setup.py to detect what system its on before it sets compiler the flags.

Why? I meet the question is so strange

Why am I observing None as the outcome of ffht.fht?

It turns out that there are some places in the algorithm, which might allow a good amount of optimization. For instance, see the following gist, which has a minimal example.

https://gist.github.com/ilyaraz/4a5d147c1a9cf9cdd25db5e92ee26f17

I realized that I don't understand what is the bottleneck for this code. It also feels like it suffers from more l1 cache misses than necessary.

We should profile and optimize it.

With all new updates fht_header_only.h stopped working (since 'fast_copy.c' is not included there). @dnbaker

I wrote a new version of FFHT [1], which is quite a bit faster and does not require the array to be aligned. Here are the results for floats with AVX (doubles are not yet supported).

[1] https://github.com/ilyaraz/ffht_codegen

I installed FFHT with Python 3.9 and got this error when trying to run example.py:

$ py example.py
Traceback (most recent call last):
  File "/Users/ahle/Dropbox (Meta)/kode/ts/FFHT/example.py", line 14, in <module>
    ffht.fht(a)
RuntimeError: PyArray_GetArrayParamsFromObject() C-API function is removed `PyArray_FromAny()` should be used at this time.  New C-API may be exposed in the future (please do request this if it would help you).

I'm on numpy version 1.21.3.

The API seems to have been depriated in 1.19: https://numpy.org/devdocs/release/1.19.0-notes.html#deprecation-of-probably-unused-c-api-functions