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
9a849add9b Optimize vector creation in get_sub_row_as_octets() 
Improves performance by ~5%
 2020-11-28 17:22:50 -08:00
Christopher Berner
8b462f5c83 Optimize processing of U matrix 
Optimize Phases 2-5 to avoid writes to the first i columns.
Additionally, use pre-computed ops from first phase to implement third &
fifth phases

This improves encoding performance by ~15%, especially on large symbol
counts
 2020-11-27 21:36:17 -08:00
Christopher Berner
a96272a0c7 Remove useless cfg guard 2020-11-23 20:00:42 -08:00
AnthonyMikh
4a6ddf1c26 Avoid bounds checking in loop 
Slicing `src` checks bounds only once instead of on every iteration of loop.
 2020-10-26 19:33:34 -07:00
Christopher Berner
4bf46ec16b Upgrade primal and pyo3 dependencies 2020-10-24 11:26:33 -07:00
Jonathan Nilsson
ab75fc1b6d OIT is copy 2020-10-22 22:49:59 -07:00
Jonathan Nilsson
a81ca51f41 I need access to the partition function for my decoder and i want to create a encoder from a ObjectTransmissionInformation 2020-10-22 22:49:59 -07:00
Jonathan Nilsson
a788b14bac Remove some clones and removed some allocations 2020-10-16 22:03:36 -07:00
Christopher Berner
95b6b5ae91 Make serde support optional 2020-08-30 09:39:39 -07:00
Christopher Berner
6330f94c4c Simplify multiplication table initialization 
Replace unrolled loops with const fn while which is new in Rust 1.46
 2020-08-29 21:23:40 -07:00
Christopher Berner
f8240da5b5 Fix incorrect symbol calculation assertion 2020-06-23 21:07:16 -07:00
Christopher Berner
dca2ad8b7c Fix Clippy warnings 2020-06-23 20:50:03 -07:00
Christopher Berner
e08c78a800 Avoid allocating excess memory 2020-05-07 10:16:43 -07:00
Christopher Berner
48a9dcc2c0 Remove dead code 2020-05-07 10:16:43 -07:00
Christopher Berner
97aa0b5003 Fix crash in Decoder when decoding large numbers of blocks 2020-03-28 14:53:34 -07:00
Christopher Berner
88a9d6d582 Fix Clippy style warning 2020-03-20 23:32:45 -07:00
Christopher Berner
69246f50b1 Add public function to calculate object to block splits 2020-03-20 22:58:09 -07:00
Christopher Berner
7847099cd7 Fix source block numbering with uneven blocks 
This fixes a critical bug where blocks with ids after ZL, see section
4.4.1.2. in RFC, were incorrectly numbered during encoding
 2020-03-14 08:38:52 -07:00
Christopher Berner
e12085c195 Add assertation from RFC to parameter calculation 2020-03-14 08:38:52 -07:00
Christopher Berner
329598c48b Implement sub block support 2020-02-25 22:50:29 -08:00
Christopher Berner
26e8b0e509 Add EncoderBuilder to allow more configuration of encoding 2020-02-24 19:09:23 -08:00
Christopher Berner
04149b42ff Fix max length assertion 
The maximum value in RFC6330 of 946270874880 is incorrect as
documented in errata id 5548
 2020-02-22 14:36:06 -08:00
Christopher Berner
6eeeb67f70 Merge Python wrapper crate into main crate 2020-02-22 13:31:16 -08:00
Christopher Berner
29131bb4d2 Parallelize repair tests 2020-02-02 10:50:28 -08:00
Christopher Berner
f9edd667dc Remove unused dbg! invocation 2020-01-26 21:41:21 -08:00
Christopher Berner
f796c55332 Remove unnecessary Vec allocation 2020-01-26 21:41:21 -08:00
Christopher Berner
7d29fd95ef Remove outdated TODOs 2020-01-26 21:41:21 -08:00
Christopher Berner
c244828d71 Various minor refactorings 2020-01-26 10:15:56 -08:00
Christopher Berner
ec54f3c838 Replace SourceBlockEncoderCache with SourceBlockEncodingPlan 2020-01-26 10:15:56 -08:00
Anders Martinsson
04786d26fd Add operation vectors for better encoding performance 
Using stored operation vectors when generating intermediate symbols make
encoding around three times faster (depends on block size).

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>
 2020-01-26 10:15:56 -08:00
Anders Martinsson
bdf5627e4c Add SSSE3 SIMD implementation 
Add SSSE3 support to be used if AVX2 support is missing and SSSE3 is available.

Signed-off-by: Anders Martinsson <anders.martinsson@intinor.se>
 2020-01-21 13:42:48 +01:00
Christopher Berner
f124b6f2be Add more extended test coverage 2020-01-19 11:08:40 -08:00
Christopher Berner
b9dde8e167 Optimize columnar storage in sparse matrix 
This reduces memory usage for large symbol counts by 10%+
 2020-01-19 11:08:40 -08:00
Christopher Berner
f0177f9311 Convert column iterator to return only 1-valued rows 2020-01-19 11:08:40 -08:00
Christopher Berner
e2ede5e61a Add assertions to check that column index is always accurate 2020-01-19 11:08:40 -08:00
Christopher Berner
87f8e7ae81 Remove logic to update column index 2020-01-19 11:08:40 -08:00
Christopher Berner
b39bce022c Optimize binary sparse vector storage 
Reduces memory usage by 10%+ for large symbol counts
 2020-01-19 11:08:40 -08:00
Christopher Berner
c07da3e667 Index adjacent nodes in graph 
Speeds up graph selection step by ~3x
 2020-01-19 11:08:40 -08:00
Christopher Berner
0b9a9cb37a Remove temporary memory allocation in adjacent nodes call 2020-01-19 11:08:40 -08:00
Christopher Berner
69187f6e2d Remove scratch graph object 2020-01-19 11:08:40 -08:00
Christopher Berner
f6829719e2 Further optimize graph memory usage 
Reduces selection helper memory usage by ~50%
 2020-01-19 11:08:40 -08:00
Christopher Berner
e5941cd5a4 Restructure graph to be more memory efficient 2020-01-19 11:08:40 -08:00
Christopher Berner
cccd950f1e Improve accuracy of graph memory tracking 2020-01-19 11:08:40 -08:00
Christopher Berner
8d3de9a4bc Document TODO 2020-01-19 11:08:40 -08:00
Christopher Berner
8d75de4d97 Reduce first phase stats memory usage 
Reduces memory by ~1MB for large symbol counts
 2020-01-19 11:08:40 -08:00
Christopher Berner
c7d16f2c89 Replace unnecessary usage of UsizeArrayMap 2020-01-19 11:08:40 -08:00
Christopher Berner
792b68638d Add memory approximation for first phase stats struct 2020-01-19 11:08:40 -08:00
Christopher Berner
7766fa4d7f Further optimize memory usage of column mapping 
Reduces memory usage by ~3% for large symbol counts
 2020-01-19 11:08:40 -08:00
Christopher Berner
d720cd7968 Optimize index mapping storage for sparse matrix 
This reduces memory usage by ~15% for large symbol counts
 2020-01-19 11:08:40 -08:00
Christopher Berner
fd93b712c8 Optimize sparse vec with byte packing into u32 
Reduces memory usage for large symbol counts by ~40%
 2020-01-19 11:08:40 -08:00
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