`check_bytes_arrays_within_dist` function added. #10

bigcat88 · 2021-08-24T17:34:15Z

Also hamming_distance_sse41_byte_max_dist and hamming_distance_loop_byte_max_dist added as underlying functions.
Added 2 tests(for input args checks and calculations check) and 1 benchmark(with result check too).
Version changed from 1.4 to 2.1

Also `hamming_distance_sse41_byte_max_dist` and `hamming_distance_loop_byte_max_dist` added as underlying functions. Added 2 tests(for input args checks and calculations check) and 1 benchmark(with result check too). Version changed from 1.4 to 2.1

mrecachinas

This LGTM, just one comment in test_check_bytes_arrays_within_dist_bench. Once you address it, I'll merge and cut a release!

mrecachinas · 2021-08-28T13:15:06Z

test/test_hexhamming.py

+)
+def test_check_bytes_arrays_within_dist_bench(benchmark, bytes1, bytes2, max_dist, result):
+    result = benchmark(check_bytes_arrays_within_dist, bytes1, bytes2, max_dist)
+    assert result == result


You can either omit this assert or rename the passed in result to expected. I'm happy for you to just omit the assert given that you're already testing check_bytes_arrays_within_dist.

remove `result` from `test_check_bytes_arrays_within_dist_bench`

bigcat88 · 2021-08-29T03:52:50Z

done

bigcat88 · 2021-09-02T02:29:56Z

Tomorrow and probably next day after too I will have free time, and I will rewrite my code. So don't merge please.

bigcat88 · 2021-09-03T01:12:04Z

How can i detect during compilation(or execution) that module was compiled on this machine?(to safely call __builtin_popcount on x86 CPU?)
__builtin_popcount generates the most optimised version with march=native, so on one PC it uses AVX, and second PC hasn't it for example.
Wish to do:
If module was compiled than __builtin for popcount can be used, if not(binary from wheel) then use the fastest algo that CPU supports.
AVX512 > AVX2 > cpu_popcount > sse_popcount > arithmetic popcount.
For non x86: Neon > cpu_popcount > arithmetic popcount.
When user builds hexhamming from source, __builtin_popcount will be the fastest and can be used...

Need this is for binary distribution w/o problems.
Maybe some flag during compilation for binary wheels, that I can check...

mrecachinas · 2021-09-03T01:17:44Z

Perhaps you could use Function Multiversioning.

bigcat88 · 2021-09-03T01:21:27Z

No, that a bit different thing....

Can be there addition arg in extra_compile_args that will be present only if user compiles hexhamming from source?

bigcat88 · 2021-09-03T01:24:29Z

something like:
https://docs.microsoft.com/en-us/cpp/build/reference/d-preprocessor-definitions?view=msvc-160
https://www.rapidtables.com/code/linux/gcc/gcc-d.html

and i will check it(assume it will have name FROM_SRC) with:
#ifdef FROM_SRC or #if defined(FROM_SRC)

or opposite name like BIN_DISTR

mrecachinas · 2021-09-03T01:37:15Z

Just so I understand, are you asking how to

automatically determine what's available (and most optimal) when someone does a python setup.py build/install, or to
automatically pick the fastest function variant available on your machine at runtime (i.e., you simply pip install hexhamming and it auto-magically figures it out)?

or both?

In the case where you're on a platform where a matching wheel exists, it won't build it from source. Therefore, the function multi-versioning might actually be useful because at runtime it will choose the most optimal available function at runtime (provided the targets are defined properly). Note: this is essentially how Tensorflow and Pytorch work with their SIMD accelerated function versions (they actually likely use dynamic library loading instead or in addition, but the concept is similar).

However, if you're on a platform where a matching wheel doesn't exist, then I believe it uses the tarball to build (i.e., it basically runs python setup.py build). In that case, it should build it according to what's available on your machine (ideally using the most optimal function, provided the macro-checking is setup accordingly).

bigcat88 · 2021-09-03T01:53:47Z

"automatically determine what's available (and most optimal) when someone does a python setup.py build/install"

PyMODINIT_FUNC 
...
    #if defined(FROM_SRC)
       // HERE ONLY when tarball building it(pip with flag --no-binary)
        p_hamming_distance_bytes = hamming_distance_bytes__builtin;
    #else
        #if defined(CPU_X86_64)
            cpu_capabilities = get_cpuid();
            if ((cpu_capabilities & bit_AVX512) == bit_AVX512)
                p_hamming_distance_bytes = hamming_distance_bytes__avx512;
            else if ((cpu_capabilities & bit_AVX2) == bit_AVX2)
                p_hamming_distance_bytes = hamming_distance_bytes__avx2;
            else if ((cpu_capabilities & bit_AVX2) == bit_POPCNT)
                p_hamming_distance_bytes = hamming_distance_bytes__asm; //cpu_popcount
            else if ((cpu_capabilities & bit_AVX2) == bit_SSE41)
                p_hamming_distance_bytes = hamming_distance_bytes__sse41;
            else
                p_hamming_distance_bytes = hamming_distance_bytes__classic;
        #else //non x86 CPU, in progress...
            p_hamming_distance_bytes = hamming_distance_bytes__classic;
        #endif
    #endif

mrecachinas · 2021-09-03T02:01:27Z

You could use CFLAGS, for example:

CFLAGS="-DFROM_SRC" python setup.py build

Off-hand, I don't know whether that would clobber existing flags (you should check). Otherwise, I suppose you could do something in setup.py like

...

extra_args = [...]
if os.environ.get("FROM_SRC"):
    extra_args.append("-DFROM_SRC")

setup(
    ...
    extra_args=extra_args,
)

need to check how it will compile on MVSC. later will write why i rewrited what was a;ready written..

bigcat88 · 2021-09-03T18:47:25Z

those what i pushed need some review and testing, i tested it with hands as i could.
Replaced ifdef SSE4.1 to ifdef CPU_X86_64 , cause there is no CPU now days that didn't support SSE4(13 years passed)...
But can revert check for SSE4.1 or implement it dynamically, if you wish...

a few benchs of this(i changed your popcnt128 to sse_popcnt128 with realization on SSE3, it was faster on my two PC(82xx,109xxk Intel CPU's):

avx2: 
elem size=512, elements before match=4.0kk, in MB=1953.125,min=0.2221665220000002, avg=0.24850279833333344
elem size=256, elements before match=4.0kk, in MB=976.5625,min=0.10947152799999982, avg=0.113585916
elem size=128, elements before match=4.0kk, in MB=488.28125,min=0.05709911199999995, avg=0.0619054171
elem size=64, elements before match=4.0kk, in MB=244.140625,min=0.028964258999999992, avg=0.03135880983333331
popcount:
elem size=512, elements before match=4.0kk, in MB=1953.125,min=0.2470361539999999, avg=0.27512743159999997
elem size=256, elements before match=4.0kk, in MB=976.5625,min=0.12591829200000015, avg=0.13021109633333328
elem size=128, elements before match=4.0kk, in MB=488.28125,min=0.06370064799999975, avg=0.06827986276666669
elem size=64, elements before match=4.0kk, in MB=244.140625,min=0.03282513900000006, avg=0.035752803400000005
sse:
elem size=512, elements before match=4.0kk, in MB=1953.125,min=0.2810797640000011, avg=0.3101610192333334
elem size=256, elements before match=4.0kk, in MB=976.5625,min=0.1433219910000001, avg=0.15382660596666664
elem size=128, elements before match=4.0kk, in MB=488.28125,min=0.07159850000000034, avg=0.0757703425666667
elem size=64, elements before match=4.0kk, in MB=244.140625,min=0.036107665000000067, avg=0.04193896580000001

And there is something a bug(dont pass all tests), need some times to found & fix it...

…nst uint8_t* a`).

bigcat88 · 2021-09-03T23:32:51Z

That what i pushed is working, but want to try one more thing for hamming_distance_bytes function for sse/avx realization.
After that will post benchmarks compared to original code in master branch(hamming_distance_bytes function).
P.SL i haven't visual studio currently and didnt make compilation test on it...(only on gcc/clang)

…n `int`(this is a high cost operation for CPU) during distance calculation, and store it only at end.

bigcat88 · 2021-09-04T02:32:37Z

that's all, finished.
there also can be done imorovement for avx calculation(use _mm256_extract_epi64 only at end after cycle) - like in my last commit, but avx already the fastest from all, so maybe later...
i currently have no arm cpu, and from tomorrow will have no free time for a week or two, so maybe later will add arm neon realiztion(need cpu or install an emulator to check what will be written)

this code is ready for binary distribution throw wheel(i think), and is not slower than previous.

bigcat88 · 2021-09-05T01:03:24Z

That what i pushed is working, but want to try one more thing for hamming_distance_bytes function for sse/avx realization.
After that will post benchmarks compared to original code in master branch(hamming_distance_bytes function).
P.SL i haven't visual studio currently and didnt make compilation test on it...(only on gcc/clang)

To compile it with studio add to start of "python_hexhamming.h" after line number 2, this strings, after that VS will ok to build it.

#if defined(_MSC_VER)
#include <cstdint>
#include <BaseTsd.h>
typedef SSIZE_T ssize_t;
#endif

mrecachinas · 2021-09-06T18:00:02Z

I pulled this into master to cut a new release with it. For further optimizations, feel free to open a new PR. Thanks for your work @bigcat88!!

mrecachinas reviewed Aug 28, 2021

View reviewed changes

mrecachinas added the enhancement New feature or request label Aug 28, 2021

mrecachinas force-pushed the master branch 2 times, most recently from 68b7299 to 335c27f Compare August 29, 2021 03:20

Update test_hexhamming.py

5a37199

remove `result` from `test_check_bytes_arrays_within_dist_bench`

mrecachinas added this to the 2.1 milestone Aug 29, 2021

bigcat88 added 3 commits September 2, 2021 18:43

demo version of header for static & dynamic CPU feauteres detect.

f174739

Merge remote-tracking branch 'origin/master'

d988dee

alpha

7385eb7

beta

978e516

need to check how it will compile on MVSC. later will write why i rewrited what was a;ready written..

bigcat88 added 2 commits September 4, 2021 00:56

fixed invalid calculation on sizes < 8(changed const char* a to `co…

6802aab

…nst uint8_t* a`).

nothing important.

8885cd2

changed hamming_distance_bytes__basic not to store each time result i…

865f28b

…n `int`(this is a high cost operation for CPU) during distance calculation, and store it only at end.

mrecachinas force-pushed the master branch 3 times, most recently from 894137a to 2e13d1a Compare September 6, 2021 17:06

mrecachinas force-pushed the master branch from 2e13d1a to 4fc4fb8 Compare September 6, 2021 17:26

Merge branch 'master' into master

457d427

mrecachinas merged commit 384cc1d into mrecachinas:master Sep 6, 2021

mrecachinas mentioned this pull request Sep 6, 2021

Add function to find closest bytestring/string in list #9

Closed

mrecachinas mentioned this pull request Feb 4, 2023

Add check_*_within_dist examples #24

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

`check_bytes_arrays_within_dist` function added. #10

`check_bytes_arrays_within_dist` function added. #10

bigcat88 commented Aug 24, 2021

mrecachinas left a comment

mrecachinas Aug 28, 2021

bigcat88 commented Aug 29, 2021

bigcat88 commented Sep 2, 2021

bigcat88 commented Sep 3, 2021 •

edited

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021

bigcat88 commented Sep 3, 2021 •

edited

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021 •

edited

bigcat88 commented Sep 3, 2021

bigcat88 commented Sep 4, 2021

bigcat88 commented Sep 5, 2021

mrecachinas commented Sep 6, 2021

check_bytes_arrays_within_dist function added. #10

check_bytes_arrays_within_dist function added. #10

Conversation

bigcat88 commented Aug 24, 2021

mrecachinas left a comment

Choose a reason for hiding this comment

mrecachinas Aug 28, 2021

Choose a reason for hiding this comment

bigcat88 commented Aug 29, 2021

bigcat88 commented Sep 2, 2021

bigcat88 commented Sep 3, 2021 • edited

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021

bigcat88 commented Sep 3, 2021 • edited

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021

mrecachinas commented Sep 3, 2021

bigcat88 commented Sep 3, 2021 • edited

bigcat88 commented Sep 3, 2021

bigcat88 commented Sep 4, 2021

bigcat88 commented Sep 5, 2021

mrecachinas commented Sep 6, 2021

`check_bytes_arrays_within_dist` function added. #10

`check_bytes_arrays_within_dist` function added. #10

bigcat88 commented Sep 3, 2021 •

edited

bigcat88 commented Sep 3, 2021 •

edited

bigcat88 commented Sep 3, 2021 •

edited