sad/raptorq
1
0
Fork 0
mirror of https://github.com/cberner/raptorq.git synced 2024-06-27 09:19:02 +00:00
Code Issues Packages Projects Releases Wiki Activity
479 Commits 1 Branch 35 Tags 1,002 KiB
master
Commit Graph

343 Commits

Author SHA1 Message Date
Christopher Berner
886075c1b0 Optimize column index memory usage 
Reduces memory usage by ~10% for large symbol counts
 2020-01-19 11:08:40 -08:00
Christopher Berner
01fcca7364 Accurately report column index memory usage 2020-01-19 11:08:40 -08:00
Christopher Berner
b60387a132 Remove unaccessed columns from X 
Reduces memory usage by ~10%
 2020-01-19 11:08:40 -08:00
Christopher Berner
083e634c7e Optimize sparse matrix to use 50-75% less memory 2020-01-19 11:08:40 -08:00
Christopher Berner
f95998b0ff Add approximate memory analysis 2020-01-19 11:08:40 -08:00
Christopher Berner
b61e4825c5 Remove unnecessary support for arbitrary width resizing 2020-01-19 11:08:40 -08:00
Christopher Berner
d8d8bc33ec Optimize dense binary matrix storage to use bitpacking 2020-01-19 11:08:40 -08:00
Christopher Berner
bf1291253b Remove unnecessary counting of values greater than one 2020-01-19 11:08:40 -08:00
Christopher Berner
059133c812 Document TODO 2020-01-19 11:08:40 -08:00
Christopher Berner
49448be936 Remove unnecessary support for non-binary values in binary matrices 2020-01-19 11:08:40 -08:00
Christopher Berner
5d57d3751e Separate binary and octet matrix classes 2020-01-19 11:08:40 -08:00
Christopher Berner
dbb0a7f7d3 Remove unnecessary normalization 2020-01-19 11:08:40 -08:00
Christopher Berner
ffee5f0d59 Remove special HDPC handling in selection helper 2020-01-19 11:08:40 -08:00
Christopher Berner
3bf4e1dfda Document usage of Errata 2 2020-01-19 11:08:40 -08:00
Christopher Berner
7ad2d331dd Remove dense row support from sparse matrix 2020-01-19 11:08:40 -08:00
Christopher Berner
7f3477d3de Separate HDPC rows from A matrix in PI solver 
The HDPC rows are only non-binary values, so store them separately
to allow for more optimizations in the future.
 2020-01-19 11:08:40 -08:00
Christopher Berner
b1f0f920c5 Document errata for RFC6330 2020-01-19 11:08:40 -08:00
Christopher Berner
f6fbcf072e Defer operations on symbols 
This makes the algorithm more cache friendly, by first performing all
the calculations on the constraint matrix, and then applying the
operations to the Symbols

Improves performance on very large symbol counts (50k) by ~10%
 2020-01-19 11:08:40 -08:00
Cem Karan
4a68f2529d feat: Derived serde::{Serialize, Deserialize} on all public types. 
This should make it possible to use serde to serialize and deserialize
encoders/decoders while they are in use.  This is makes it possible to
ship them between processes as needed.
 2020-01-09 19:34:21 -08:00
Christopher Berner
647e937c54 Optimize col index handling 2020-01-06 18:27:02 -08:00
Christopher Berner
13b1d0200f Remove unnecessary Symbol cloning 2020-01-06 18:27:02 -08:00
Christopher Berner
63208df2b5 Improve dense row handling in sparse matrix 
* support resize()
* use logical col indices
 2020-01-06 18:27:02 -08:00
Christopher Berner
55d42fdee2 Reuse scratch memory for graph 2020-01-06 18:27:02 -08:00
Christopher Berner
9d0af2dcad Appropriately size col index vectors 2020-01-06 18:27:02 -08:00
Christopher Berner
2fec2cb9d7 Remove useless loop 2020-01-06 18:27:02 -08:00
Christopher Berner
2bad8466fa Optimize HDPC row storage in sparse matrix 2020-01-06 18:27:02 -08:00
Christopher Berner
0cecda508c Split sparse matrix into separate file 2020-01-04 16:12:56 -08:00
Christopher Berner
b42b84a746 Refactor iterators into separate file 2020-01-04 16:12:56 -08:00
Christopher Berner
79ae52cfb1 Separate SparseValuelessVec from SparseOctetVec 2020-01-04 16:12:56 -08:00
Christopher Berner
4e1dc4fa93 Avoid accessing internal sparse vector fields in matrix 2020-01-04 16:12:56 -08:00
Christopher Berner
f0f0f98247 Merge SparseVec into SparseOctetVec 2020-01-04 16:12:56 -08:00
Christopher Berner
8f8637be8a Move SparseVec into separate file 2020-01-04 16:12:56 -08:00
Christopher Berner
876d3c5cac Refactor calls to binary_search into helper method 2020-01-04 16:12:56 -08:00
Christopher Berner
5b7f1b7441 Fix remaining Clippy warnings 2019-12-25 12:02:54 -08:00
Christopher Berner
ffd6160099 Fix various stylistic Clippy issues 2019-12-25 12:02:54 -08:00
Christopher Berner
cff96c6779 Make Clippy cast_ptr_alignment suppressions more granular 2019-12-23 12:04:05 -08:00
Christopher Berner
12a0d579a4 Fix potentially undefined reads/writes to unaligned memory 2019-12-23 12:04:05 -08:00
Christopher Berner
7eb6542865 Fix many Clippy warnings and errors 2019-12-23 12:04:05 -08:00
Christopher Berner
c8fd9bcbff Format code with rustfmt and add format check 2019-12-23 12:04:05 -08:00
Christopher Berner
0ea2e92a81 Add extended test to cover all symbol counts 
This test takes ~12hrs on a modern CPU
 2019-12-23 10:35:36 -08:00
Christopher Berner
b7d921a78b Fix generation of constraint matrix for 1698 and 8837 source symbols 
The gamma matrix was being generated incorrectly due to casting
(i - j) to u8 instead of wrapping it to 255 values
 2019-12-22 22:48:29 -08:00
Christopher Berner
057b063554 Fix mtu calculation in test to speed it up 2019-12-22 19:15:14 -08:00
Christopher Berner
a0e304a59d Make assertions stricter in Enc[] implementation 2019-12-22 19:15:14 -08:00
Christopher Berner
cd4208e5c3 Add missing semicolon 
Has no functional effect
 2019-12-22 19:15:14 -08:00
Felix Schorer
336560db4a Fix trying to apply padding when no padding is required 2019-12-22 12:34:12 -08:00
Vincent Dagonneau
7c4ebf812a Divided the decode method on the Decoder in two distinct methods for easier interaction: add_new_packet processes a new packet and get_result actually decodes the processed packets. 2019-05-06 17:56:41 -07:00
Christopher Berner
a87f009979 Add additional assertions to codec 2019-04-14 16:51:38 -07:00
Christopher Berner
0ba42236d1 Optimize systematic constant lookups 2019-04-14 13:40:43 -07:00
Christopher Berner
301f7ee03d Simplify and optimize sparse FMA 2019-04-14 13:18:31 -07:00
Christopher Berner
435e2c1207 Refactor SourceBlockDecoder.decode() to take an iterator 2019-04-13 22:16:08 -07:00
Christopher Berner
b2399469b2 Fix decoding crash 
Fixes an issue in column swapping logic, where non-zeros might be
swapped into the V matrix instead of zeros
 2019-04-13 16:30:25 -07:00
Christopher Berner
b32fa67e05 Optimize hint dense column 2019-04-11 22:27:06 -07:00
Christopher Berner
8286361f24 Optimize get_col_iter() 2019-04-11 17:51:18 -07:00
Christopher Berner
4cfef50cf3 Add more tests and verification code 2019-04-10 23:34:34 -07:00
Christopher Berner
6f95146bf8 Remove heuristic 2019-04-10 18:23:17 -07:00
Christopher Berner
3858944c18 Fix potentially incorrect col tracking in fma() 2019-04-10 18:21:10 -07:00
Christopher Berner
228a3bdc7f Use sparse math more aggressively now that it's faster 2019-04-09 21:46:31 -07:00
Christopher Berner
5eb972c21f Extract constant from loop 2019-04-09 21:30:25 -07:00
Christopher Berner
777218debd Optimize sparse matrix column swapping 2019-04-09 21:21:25 -07:00
Christopher Berner
e0ce5f3b55 Add logical row mapping 
Improves perf by ~50% on large matrices
 2019-04-09 18:38:07 -07:00
Christopher Berner
1cc5502fe2 Expand matrix sparsity benchmark 2019-04-08 20:43:13 -07:00
Christopher Berner
c1b3be12c5 Remove dead code 2019-04-08 19:56:33 -07:00
Christopher Berner
44f529214c Optimize row selection when r=1 2019-04-08 19:08:09 -07:00
Christopher Berner
f57bca53bf Optimize constraint matrix generation 2019-04-08 18:15:21 -07:00
Christopher Berner
3a3f739fae Enable sparse matrix math at >= 1000 symbols 2019-04-07 21:40:01 -07:00
Christopher Berner
6e18062b03 Rename freeze_columns() 2019-04-07 21:02:53 -07:00
Christopher Berner
fbd59bf982 Add fast path to column swapping for sparse 2019-04-07 20:09:51 -07:00
Christopher Berner
58550e3dd3 Ensure that optimize introduce previously is safe 
Commit that introduce this: 59e88ad7581c2f7352e1054b40629e8cb7a9c572
 2019-04-07 19:59:17 -07:00
Christopher Berner
6e4f8ecf32 Make stats resizing more sparse friendly 2019-04-07 18:53:59 -07:00
Christopher Berner
d4e16d8b98 Heuristic to optimize FMA on large sparse vectors 2019-04-07 18:44:38 -07:00
Christopher Berner
59e88ad758 Optimize to fifth PI phase for sparse 2019-04-07 17:55:51 -07:00
Christopher Berner
0d531de69e Further optimize PI solver for sparse matrices 2019-04-07 17:33:58 -07:00
Christopher Berner
e01a3b987c Move tests to fix Travis 2019-04-07 17:13:44 -07:00
Christopher Berner
6ab457f6a4 Optimize sparse FMA for most common case 
This improves sparse perf by ~4x
 2019-04-07 16:50:50 -07:00
Christopher Berner
f063d3114d Optimize sparse matrix density storage with more hinting 2019-04-07 16:18:29 -07:00
Christopher Berner
6c73ee267c Optimize sparse matrix with block dense right side 2019-04-07 15:31:00 -07:00
Christopher Berner
e53e82d785 Fix bad optimization in sparse matrix 
Note: setting zero isn't a no-op, since there might be a non-zero value
already
 2019-04-07 11:26:33 -07:00
Christopher Berner
fca4f14c06 Add more sparse tests and framework for enabling sparse math 2019-04-07 10:30:12 -07:00
Christopher Berner
1ff495f445 Improve test coverage 2019-04-07 09:59:42 -07:00
Christopher Berner
21e2133f7f Optimize PI decoder to be more sparse friendly 2019-04-06 23:15:32 -07:00
Christopher Berner
b3b6ab0fe9 Add TODOs noting places that may need to be optimized for sparse 2019-04-06 21:02:30 -07:00
Christopher Berner
7906ec47fb Optimize first phase selection helper resize() 
Because we always zero out all following rows in the leading column,
the work it was doing was unnecessary
 2019-04-06 20:51:33 -07:00
Christopher Berner
a66b49d1e7 Optimize sparse matrix to elide zeros created by FMA 2019-04-06 20:06:40 -07:00
Christopher Berner
d12a2485bf Optimize column swapping in SparseOctetMatrix 2019-04-06 19:56:32 -07:00
Christopher Berner
28cad084e4 Refactor SparseOctetVec 2019-04-06 18:31:53 -07:00
Christopher Berner
953d0f6c8a Optimize SparseOctetVec.swap() 2019-04-06 16:25:48 -07:00
Dodo
f868265380 .keys() returns a DoubleEndedIterator 2019-04-06 15:32:02 -07:00
Christopher Berner
3787690112 Optimize SparseOctetVec to use a sorted Vec instead of a HashMap 2019-04-06 14:46:15 -07:00
Christopher Berner
30c27a62ca Refactor SparseOctetMatrix 2019-04-06 11:01:52 -07:00
Christopher Berner
4268e4b508 Add sparse matrix implementation 
Note: Lots of room for optimization still!
 2019-04-06 09:45:12 -07:00
Christopher Berner
5817ec9765 Refactor OctetMatrix into a trait 2019-04-05 21:18:25 -07:00
Christopher Berner
1cb16e4636 Refactor OctetMatrix interface to make it easier to sparsify 2019-04-05 20:13:00 -07:00
Luca Bruno
09a1db06d9 mulassign/fallback: make safety invariants explicit 
This simplifies the non-SIMD mulassign, making its safety invariants
explicit and documented.
 2019-03-30 16:04:21 -07:00
Luca Bruno
e61e1eb2d4 coded: consume symbol bytes 
This allows Symbol bytes to be directly consumed by encoder and decoder,
avoiding some extra allocations.
 2019-03-30 15:57:56 -07:00
Luca Bruno
9fe45d6d76 decoder: avoid zero-symbols casts 
This replaces zero-symbols casts with statically checked "Into" type
conversions.
 2019-03-30 15:57:56 -07:00
Luca Bruno
631e2f8f97 decoder: misc cleanups 
This is a minor cleanup pass to avoid unnecessary cloning and
unwrapping in the decoder.
 2019-03-29 19:09:41 -07:00
Luca Bruno
38df97cce1 raptorq: rustfmt whole project 2019-03-28 21:57:30 -07:00
Luca Bruno
a55116e637 rustfmt: do not format tables 2019-03-28 21:57:30 -07:00
Christopher Berner
c0d0e13b43 Add serialization methods 2019-03-23 21:12:47 -07:00
Christopher Berner
3bbe9b8ef1 Cleanup public interfaces 2019-03-23 20:35:28 -07:00
Christopher Berner
91fa69a130 Gate some public functions with "benchmarking" feature 2019-03-23 14:42:19 -07:00
Christopher Berner
ea913f0ddd Precompute P1 
Improves performance by ~1% and removes primal dependency
 2019-03-23 14:15:06 -07:00
Christopher Berner
2ec675065b Add unit test 2019-03-23 13:53:10 -07:00
Christopher Berner
497c1613ff Remove rand dependency 2019-03-23 13:48:11 -07:00
Christopher Berner
919b4a0f5b Reduce row swaps 
Improves performance by ~1%
 2019-03-23 13:29:00 -07:00
Christopher Berner
1431ace8bf Make test more robust and resolve TODO 2019-03-23 13:12:08 -07:00
Christopher Berner
dad38875a8 Replace petgraph with custom connected components code 
Improves performance by ~20%
 2019-03-23 12:22:27 -07:00
Christopher Berner
f288654525 Update to 2018 edition 2019-03-22 18:25:07 -07:00
Christopher Berner
2d92876aa4 Remove Octet::static_init() and use const fn instead 2019-03-21 23:24:53 -07:00
Christopher Berner
a8347df59d Switch to runtime SIMD detection 2019-03-21 21:50:21 -07:00
Christopher Berner
bb2f576453 Add conveniance call to Octet::static_init() in decoder and encoders 2019-03-20 17:49:54 -07:00
Christopher Berner
91c6745257 Make EncodingPacket public 2019-03-20 17:45:28 -07:00
Christopher Berner
0644794488 Add Encoder and Decoder that can span multiple blocks 2019-02-20 20:52:44 -08:00
Christopher Berner
7c361d698e Add Object Transmission Information struct 2019-02-18 23:25:56 -08:00
Christopher Berner
ca552aaa55 Move PI solver to separate file 2019-02-18 17:02:54 -08:00
Christopher Berner
5e2c7a9077 Optimize mul_row() implementation 2019-02-18 10:48:06 -08:00
Christopher Berner
a20f894c52 Support extra repair symbols when decoding 2019-02-18 10:34:43 -08:00
Christopher Berner
c8cddfca53 Address TODO 2019-02-17 22:36:39 -08:00
Christopher Berner
bf5a64815a Replace &Vec with &[u8] in octets.rs 2019-02-16 18:08:16 -08:00
Christopher Berner
fc0ae5d162 Keep histrogram to accelerate computation of "r" 
Improves performance by 5%
 2019-02-16 10:56:24 -08:00
Christopher Berner
35145f43c8 Reduce memory allocation for graph 2019-02-15 23:45:34 -08:00
Christopher Berner
0ccc423bfd Add specialized UsizeArrayMap 2019-02-15 23:25:40 -08:00
Christopher Berner
b5360175ee Fix initial end column in row selection stats 2019-02-15 22:48:23 -08:00
Christopher Berner
27d1e75ab9 Fix bug in row selection 2019-02-15 22:33:40 -08:00
Christopher Berner
ae26fbfe0d Refactor row selection code 2019-02-15 22:23:16 -08:00
Christopher Berner
123d5ab2c1 Optimize row selection stats tracking 2019-02-15 21:56:48 -08:00
Christopher Berner
dc5c4c9cce Replace panic!() with unreachable!() 2019-02-15 21:25:41 -08:00
Christopher Berner
2abaab93cb Restructure bin targets 2019-02-15 21:14:10 -08:00
Christopher Berner
c93140968e Document where HDPC rows are defined 2019-02-15 20:58:13 -08:00
Christopher Berner
c5b70b66c7 Replace HashSet with Vec 
Improves perf 6%
 2019-02-14 21:54:23 -08:00
Christopher Berner
34f6ba3a46 Reduce memory allocation 
Improves perf by 10%
 2019-02-14 21:32:09 -08:00
Christopher Berner
f61c13ec6f Replace Vec with array 2019-02-13 22:56:04 -08:00
Christopher Berner
36eca029a4 Use with_capacity when possible to create vectors 
Improves perf ~3%
 2019-02-13 22:41:42 -08:00
Christopher Berner
8622195e32 Optimize decoder to do less memory allocation 
Improve decoder repair perf by ~15%
 2019-02-13 22:29:15 -08:00
Christopher Berner
1831b7d97f Cleanup encoder code 2019-02-13 21:56:25 -08:00
Christopher Berner
f20204d045 Require borrowing for matmul 2019-02-13 21:39:35 -08:00
Christopher Berner
1f0a6639b4 Remove unneeded OctetMatrix methods 2019-02-13 21:35:26 -08:00
Christopher Berner
2937619983 Cleanup Octet tests 2019-02-13 21:31:09 -08:00
Christopher Berner
f85d6c5075 Remove excess clone()'ing 
Improves performance by 15%
 2019-02-12 23:04:30 -08:00
Christopher Berner
2efe39012f Replace drain() with truncate() 2019-02-12 23:01:41 -08:00
Christopher Berner
9dc023e0f2 Add new benchmark and reduce calls to .clone() 2019-02-12 22:01:35 -08:00
Christopher Berner
966ed6d666 Refactor first phase decoding 2019-02-12 21:18:19 -08:00
Christopher Berner
42fab82742 Prevent inlining some functions to make profiling easier 2019-02-12 21:07:05 -08:00
Christopher Berner
a7966934dd Add per phase tracking of symbol XOR and MUL ops 2019-02-12 18:08:24 -08:00
Christopher Berner
14ede8e96e Incrementally compute row selection stats for first phase 
Improve performance by ~5%
 2019-02-11 23:34:10 -08:00
Christopher Berner
195843fe66 Fix compiler warnings 2019-02-11 21:59:54 -08:00
Christopher Berner
5dd3a0bc18 Implement sorting by original degree 2019-02-11 18:21:52 -08:00
Christopher Berner
e84bdfbd41 Resolve ambiguity about graph construction 2019-02-11 17:59:10 -08:00
Christopher Berner
f8d8d53c52 Fix compiler warnings and add a test 2019-02-10 23:41:41 -08:00
Christopher Berner
cec0f2bdd1 Add SIMD implementation of ones and non-zeros counting 2019-02-10 23:09:13 -08:00