<commit_before>== LvvLib - C++ utility library
:gh-ll:		http://github.com/lvv/lvvlib/tree/master/


Initially collection of headers that I used in my projects.  'LVV' are my initials (<NAME>).
Needs some cleanup, dependency pruning and documentation. 

=== http://github.com/lvv/lvvlib/tree/master/array.h[array.h]

It is enhanced version of http://http://www.boost.org/doc/libs/1_37_0/doc/html/array.html[`boost::array`] 
which is plain C array wrapped in class to make it STL compatible
container.  If you look in such array in debugger its looks exactly like C
arrays (which means you can freely cast to and from C array). Because it
doesn't have constructor, it can be initialised like C arrays:

  lvv::array<float,3> A = {{1., 2., 3.}}

Second set of curly braces needed because this is an array inside a class. 
There are no mallocs,  no extra pointers, no extraneous class members.
GCC 4.4 promoted `boost::array` to `tr1::array`.

.lvv::array have following added capabilities:
- Vector operation:   `A1 += A2;   cout << A1;`
- Optimized template specialization for specific combination of CPU capabilities,  array size and type.
	* explicit SSE vectorization (gcc not very good yet in auto-vectorization).
	* parallelization with OpenMP
	* out-of order execution optimization
- Index of first element defaults to 0, but can be any number.
- Index value tested if it is in valid range when `NDEBUG` macro  is not defined (not optimized compile). 
- basic linear algebra functions:  `norm2(A)`, `distance_norm2(A1,A2)`, `dot_product(A1,A2)`, etc

==== Specialization
Template specialization is technique which allow with zero overhead to select
most appropriate implementation.  Zero overhead means no run-time
implementation-selection code, everything done in compile time. This is similar
to run time CPU dispatch which is done in compile time. Selection logic is based on data-type, performed
operation, target cpu, array size.  Below is benchmark of specialised
operations. Benchmarks are done on Core2 Duo, 2.2Ghz, with GCC-4.4.  Benchmark
source is at `b-*.h` files. 

.Sum of 100,000,000 float-s with values {1, 2, 1, 2, 1, 2 ...}
[cols="^3,^1,^2, 16",frame="topbot",options="header"]
|=============================================================================================
| *Ticks per cycle* | *Computed Value*  | *Method* 		| *Source*
| 1.74              | 1.5e+08           | lvv::array member fn	| `float  sum = A.sum();`  // same as `sum<sse>()`
| 1.67              | 1.5e+08           | explicit OpenMP	| `float  sum = A.sum<omp>();`
| 3.14              | 1.5e+08           | double for-cycle	| `double sum=0;  for (int i=0 ; i<N; i++) sum += A[i];`
| 3.06              | 3.355e+07		| float  for-cycle	| `float  sum=0;  for (int i=0 ; i<N; i++) sum += A[i];`
| 3.06              | 3.355e+07		| std::accumulate<float>()| `float  sum = accumulate(A.begin(), A.end(), 0.f));`
|=============================================================================================
Note that two last lines have big rounding error. Benchmark source is at b-array.cc.
Further optimizatin is difficult as it is obsiously memory bound. 

.Maximum of 100,000,000 float-s
[cols="^1,6",frame="topbot",options="header"]
|=============================================================================================
| *Ticks per cycle* |  *Source*
| 1.63              |  `float  max = A.max()`
| 5.81              |  `float  max=0;  for (size_t i=0; i<N; i++) if (A[i] >  max) max = A[i];`
| 1.88              |  OpenMP (source same as above, 2xCPU, no check for race)
| 5.81              |  STL: `float  max = *std::max_element (A.begin(), A.end());`
| 1.67              |  SSE: `__m128 m = mk_m128(A[0]);  for (size_t i=4; i<N; i+=4) { m = _mm_max_ps(m, mk_m128(A[i]) ); } ...`
|==============================================================================================

So far I implemented only combinations needed for my work. Hopefully there will
be less blank space in table bellow as I will have more time or there will be outside contributions.

.Implemented combinations
[cols="1,^1,^1,^1,^1,^1,^1,^1,^1",frame="topbot",options="header"]
|=============================================================================================
| *Type*         |  *sum*  | *max* | *min* | *lower_bound* | *find* | *V1 += V2* | *V1 -= V2* | *...*
| *generic*      |  std::  |  std::|       |   std::       | std::  | for-loop   | for-loop   |
| *float*        |  sse    |  sse  |       |               |        |            |            |
| *double*       |         |       |       |               |        |            |            |
| *long double*  |         |       |       |               |        |            |            |
| *int8_t*       |         |       |       |               |        |            |            |
| *int16_t*      |         |  sse2 |       |               |        |            |            |
| *int32_t*      |         |       |       |               |        |            |            |
| *int64_t*      |         |       |       |               |        |            |            |
| *uint8_t*      |         |       |       |               |        |            |            |
| *uint16_t*     |         |       |       |               |        |            |            |
| *uint32_t*     |         |       |       |               |        |            |            |
| *uint64_t*     |         |       |       |               |        |            |            |
|==============================================================================================


=== *eq()* - numeric comparison template function (http://github.com/lvv/lvvlib/tree/master/math.h[math.h])
Used for numeric comparison in generic programming.  For floating point types
comparison precision will scale proportionally to type used and will still work if
integral type used. If different types are compared, ulp of lowest precision type is used. 

Error in floating point expression is proportional to absolute value of a
number and precision of a type used.  Error will be bigger for `10000` than for<commit_msg>-- docs<commit_after>== LvvLib - C++ utility library

//  HTML rendered version of this file is at:  http://volnitsky.com/project/lvvlib

:gh-ll:		http://github.com/lvv/lvvlib/tree/master/

Initially collection of headers that I used in my projects.  'LVV' are my initials (<NAME>).
Needs some cleanup, dependency pruning and documentation. 

=== http://github.com/lvv/lvvlib/tree/master/array.h[array.h]

Enhanced version of http://www.boost.org/doc/libs/1_37_0/doc/html/array.html[`boost::array`] 
which is plain C array wrapped in class to make it STL compatible
container.  If you look in such array in debugger its looks exactly like C
arrays (which means you can freely cast to and from C array).
There are no mallocs,  no extra pointers, no extraneous class members.
Because it doesn't have constructor, it is an agrigate type, meaning that it can be initialised like C arrays,
some vector operation are supported. Sample use:

---------------------------------
using lvv:array;
array<float,3>	A = {{1., 2., 3.}};
array<float,3>	B;
B = 1.;
A += B;
cout  << "vector A: "  <<  A  << endl;
cout  << "vector B: "  <<  B  << endl;
cout  << "dot product: "  <<  dot_prod(A,B)  << endl;
------------------------------

Second set of curly braces needed because this is an array inside a class. 
All `B` elements are assigned scalar `1.f`, then vector `B` added to `A`, you can
send `lvv::array` to `iostream`.
GCC 4.4 promoted `boost::array` to `tr1::array`.

.lvv::array have following added capabilities:
- Vector operation
- Optimized template specialization for specific combination of CPU capabilities,  array size and type.
	* explicit SSE vectorization (gcc not very good yet in auto-vectorization).
	* parallelization with OpenMP
	* out-of order execution optimization
- Index of first element defaults to 0, but can be any number.
- Index value tested if it is in valid range when `NDEBUG` macro  is not defined (not optimized compile). 
- basic linear algebra functions:  `norm2(A)`, `distance_norm2(A1,A2)`, `dot_product(A1,A2)`, etc

==== Specialization
Template specialization is technique which allow with zero overhead to select
most appropriate implementation.  Zero overhead means no run-time
implementation-selection code, everything done in compile time. This is similar
to run time CPU dispatch, but it is done in compile time. Selection logic is based on data-type, performed
operation, target cpu, array size.  Below is benchmark of specialised
operations. Benchmarks are done on Core2 Duo, 2.2Ghz, with GCC-4.4.  Benchmark
source is at `b-*.h` files. 

.Sum of 100,000,000 float-s with values {1, 2, 1, 2, 1, 2 ...}
[cols="3,^2,^2, 16",frame="topbot",options="header"]
|============================================================================================
| *Method* 			| *Ticks per cycle* | *Computed Value*  | *Source*
| lvv::array member fn		| 1.74              | 1.5e+08           | `float  sum = A.sum();`  // same as `sum<sse>()`
| lvv::array, explicit OpenMP	| 1.67              | 1.5e+08           | `float  sum = A.sum<omp>();`
| plain for-loop, double	| 3.14              | 1.5e+08           | `double sum=0;  for (int i=0; i<N; i++) sum += A[i];`
| plain for-loop, float		| 3.06              | 3.35e+07		| `float  sum=0;  for (int i=0; i<N; i++) sum += A[i];`
| std::accumulate<float>()	| 3.06              | 3.35e+07		| `float  sum = accumulate(A.begin(), A.end(), 0.f));`
|============================================================================================
Note that two last lines have big rounding error. Benchmark source is at b-array.cc.
Further optimizatin is difficult as it is obviously memory bound. 

.Maximum of 100,000,000 float-s
[cols="2,^1,11",frame="topbot",options="header"]
|=======================================================================================================================
| *Method* 		| *Ticks per cycle* | * *Source*
| lvv::array member fn	| 1.63              | `float  max = A.max()`
| plain for-loop	| 5.81              | `float  max=0;  for (size_t i=0; i<N; i++) if (A[i] >  max) max = A[i];`
| OpenMP		| 1.88              | `(source same as above, 2xCPU, no check for race)`
| std::max_element()	| 5.81              | `float  max = *std::max_element (A.begin(), A.end());`
| SSE intrinsics	| 1.67              | `__m128 m = mk_m128(A[0]);  for (size_t i=4; i<N; i+=4) { m = _mm_max_ps(m, mk_m128(A[i]) ); } ...`
|========================================================================================================================

So far I implemented only combinations needed for my work. Hopefully there will
be less blank space in table bellow as I will have more time or there will be outside contributions.

.Implemented combinations
[cols="1,^1,^1,^1,^1,^1,^1,^1,^1",frame="topbot",options="header"]
|=============================================================================================
| *Type*         |  *sum*  | *max* | *min* | *lower_bound* | *find* | *V1 += V2* | *V1 -= V2* | *...*
| *generic*      |  std::  |  std::|       |   std::       | std::  | for-loop   | for-loop   |
| *float*        |  sse    |  sse  |       |               |        |            |            |
| *double*       |         |       |       |               |        |            |            |
| *long double*  |         |       |       |               |        |            |            |
| *int8_t*       |         |       |       |               |        |            |            |
| *int16_t*      |         |  sse2 |       |               |        |            |            |
| *int32_t*      |         |       |       |               |        |            |            |
| *int64_t*      |         |       |       |               |        |            |            |
| *uint8_t*      |         |       |       |               |        |            |            |
| *uint16_t*     |         |       |       |               |        |            |            |
| *uint32_t*     |         |       |       |               |        |            |            |
| *uint64_t*     |         |       |       |               |        |            |            |
|==============================================================================================


=== *eq()* - numeric comparison template function (http://github.com/lvv/lvvlib/tree/master/math.h[math.h])
Used for numeric comparison in generic programming.  For floating point types
comparison precision will scale proportionally to type used and will still work if
integral type used. If different types are compared, ulp of lowest precision type is used. 

Error in floating point expression is proportional to absolute value of a
number and precision of a type used.  Error will be bigger for `10000` than for
{'fraction_non_alphanumeric': 0.21322275616183536, 'fraction_numerical': 0.025422415129437298, 'mean_word_length': 2.248489425981873, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 62, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2694779', 'n_tokens_mistral': 3981, 'n_tokens_neox': 3684, 'n_words': 1208}