All Projects → stgatilov → linear-vs-binary-search

stgatilov / linear-vs-binary-search

Licence: MIT license
Comparing linear and binary searches

Programming Languages

C++
36643 projects - #6 most used programming language
python
139335 projects - #7 most used programming language
Batchfile
5799 projects

Projects that are alternatives of or similar to linear-vs-binary-search

Seqan
SeqAn's official repository.
Stars: ✭ 386 (+1278.57%)
Mutual labels:  high-performance, simd
Nnpack
Acceleration package for neural networks on multi-core CPUs
Stars: ✭ 1,538 (+5392.86%)
Mutual labels:  high-performance, simd
WeightedRandomSelector
Very fast C# class for weighted random picking.
Stars: ✭ 117 (+317.86%)
Mutual labels:  binary-search, linear-search
Python Algorithms
Code for various YouTube video lessons + extras
Stars: ✭ 26 (-7.14%)
Mutual labels:  binary-search
hpc
Learning and practice of high performance computing (CUDA, Vulkan, OpenCL, OpenMP, TBB, SSE/AVX, NEON, MPI, coroutines, etc. )
Stars: ✭ 39 (+39.29%)
Mutual labels:  simd
QUB DW HighPerformancePython
Code and more for the QUB Development Weeks event 'High Performance Python'
Stars: ✭ 79 (+182.14%)
Mutual labels:  high-performance
pacxx-llvm
Programming Accelerators with C++ (PACXX)
Stars: ✭ 57 (+103.57%)
Mutual labels:  high-performance
SCNMathExtensions
Math extensions for SCNVector3, SCNQuaternion, SCNMatrix4
Stars: ✭ 32 (+14.29%)
Mutual labels:  simd
qHilbert
qHilbert is a vectorized speedup of Hilbert curve generation using SIMD intrinsics
Stars: ✭ 22 (-21.43%)
Mutual labels:  simd
Amplifier.NET
Amplifier allows .NET developers to easily run complex applications with intensive mathematical computation on Intel CPU/GPU, NVIDIA, AMD without writing any additional C kernel code. Write your function in .NET and Amplifier will take care of running it on your favorite hardware.
Stars: ✭ 142 (+407.14%)
Mutual labels:  simd
Quickenshtein
Making the quickest and most memory efficient implementation of Levenshtein Distance with SIMD and Threading support
Stars: ✭ 204 (+628.57%)
Mutual labels:  simd
LruClockCache
A low-latency LRU approximation cache in C++ using CLOCK second-chance algorithm. Multi level cache too. Up to 2.5 billion lookups per second.
Stars: ✭ 35 (+25%)
Mutual labels:  high-performance
SSCTaglistView
Customizable iOS tag list view, in Swift.
Stars: ✭ 54 (+92.86%)
Mutual labels:  high-performance
heyoka.py
Python library for ODE integration via Taylor's method and LLVM
Stars: ✭ 45 (+60.71%)
Mutual labels:  simd
psimd
Portable 128-bit SIMD intrinsics
Stars: ✭ 48 (+71.43%)
Mutual labels:  simd
42nd-at-threadmill
A SIMD-accelerated concurrent hash table.
Stars: ✭ 49 (+75%)
Mutual labels:  simd
penguinV
Simple and fast C++ image processing library with focus on heterogeneous systems
Stars: ✭ 110 (+292.86%)
Mutual labels:  simd
minstant
Performant time measuring in Rust
Stars: ✭ 109 (+289.29%)
Mutual labels:  high-performance
clue
a extremely high performance log library for android. 高性能的Android日志库
Stars: ✭ 27 (-3.57%)
Mutual labels:  high-performance
SIMDArray
SIMD enhanced Array operations
Stars: ✭ 123 (+339.29%)
Mutual labels:  simd

linear-vs-binary-search

These are the materials for the blog post: https://dirtyhandscoding.github.io/posts/performance-comparison-linear-search-vs-binary-search.html

It compares several implementations of linear or binary search intended to find position within a sorted array. Here is the main plot with results (Broadwell 2 Ghz CPU), see the blog post for more information.

Contents

All the C++ code is in search.cpp file, see more comments inside it.

Tiny script c.bat gives the command line for compiling search.cpp using MSVC compiler. Aside from the obvious /O2 setting there, also /arch:AVX2 and /D NDEBUG are important for proper performance measurements. Also it contains commented command line for GCC compilation, which also needs one specific flag -fno-strict-overflow.

The python scripts work as follows (Python 3 is required). First you run collectdata.py, which takes search.cpp source, copies it into search_tmp.cpp with some changes, compiles it using c.bat script and runs search_tmp.exe to generate text logs into /res subdirectory. Then you run makeplots.py, which takes all logs in /res subdirectory and generates png images with plots (in the same subdirectory).

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].