libor-m / adark Goto Github PK

What functionality is missing?
64-bit words operation.

Why is it so important to have it?
More efficient comparison of strings.
Allows for non-restricted length of Huffman codes.
Today's consumer CPU's are mostly 64-bit.

What are the implementation stages:
1. Introduce an abstraction of the comparison type.
2. Add a pre-processor directive.
3. Compare performance.

What functionality is missing?
Bit array is not necessary.

Why is it so important to have it?
Memory requirements can be N/4 lower.

What are the implementation stages:
1. Pack some bits into the suffixes.
2. Remove the array.
3. Test and benchmark.

What functionality is missing?
We are using only a single line of a 2D texture, so GL limits our input size by 
8k. By utilizing more lines we can get larger blocks support (at least 1<<26 
size).

Why is it so important to have it?
8k is an extremely small limit for the input size.

What are the implementation stages:
1. Upgrade scatter shader
2. Fix texture creation logic

What functionality is missing?
Itoh-Tanaka 2nd order sorting.

Why is it so important to have it?
Greatly reduces the number of suffixes to sort.

What are the implementation stages:
1. Add first-order statistics (R2).
2. Add classical IT-2.
3. Choose the smallest group to sort.
4. Add command-line options.

What functionality is missing?
Ability to sort LML instead of LMS.

Why is it so important to have it?
LML start with the beginnings of the groups. It would be more efficient to 
radix-sort them.

What functionality is missing?
We need a fastest sorting network.

What is the benefit of implementing the support for it?
Sorting network stage will not (probably) be a bottleneck any more.

What are the implementation stages:
1. Understand the method and the proof
2. Find/Create iterative form
3. Translate to OpenGL

What functionality is missing?
Reverse transformation.

Why is it so important to have it?
Practical usage.

What are the implementation stages:
1. Implement basic reverse BWT.
2. Add command-line options.
3. Improve with VY idea (see below).

What functionality is missing?
Header files.

Why is it so important to have it?
Forward declarations in C are error-prone, because the linker does not check 
that function parameters match.

What are the implementation stages:
1. Add header files.
2. Fix code files.

What functionality is missing?
A tool to count the size of each ITN group in a particular file.

Why is it so important to have it?
To estimate the benefit on a data set. To analyze the data.

What are the implementation stages:
1. Implement the tool!

What functionality is missing?
Support for input data of the size that is not power of 2. This affects several 
stages of the pipeline.

Why is it so important to have it?
We have to be able to transform any input given.

What are the implementation stages:
1. Upgrade OEM sorting procedure
2. Upgrade hierarchical stages
3. Tweak scatter stage that requires N=4k

What functionality is missing?
Bucket access has a lot of cache misses. This is even worse on a4 due to the 
fact 2-nd order radix is used. We can use the same tricks a7 does.

Why is it so important to have it?
Can speed up the linear thing by approx 25%.

What functionality is missing?
Archon4 always sorts A<B>=C suffixes. Instead, it can choose either A>B<=C or 
A>B>=C together with A<B<=C. Any of these 3 groups is sufficient to deduce all 
other suffixes, so we can choose the smallest one to sort. While in average all 
of them are 1/3 of the input, the actual proportion can depend heavily on the 
nature of the data.

Why is it so important to have it?
It can reduce the number of suffixes required to sort without any performance 
penalty, just with a bit of more (localized) complexity.

What are the implementation stages:
1. Compute the theory behind each group.
2. Implement 3 different inducing paths.
3. Add logic to choose the best one.
4. Test to compare with a4r0.

What functionality is missing?
Separate code paths of all ITN subgroups.

Why is it so important to have it?
Reduces the memory requirements to 5n.

What functionality is missing?
Source and binaries of archon BWT and dark compressors.

Why is it so important to have it?
To have a complete profile of my BWT-based compression research.

What are the implementation stages:
1. Add OpenDark, dark, archon2 and archon3 to downloads.
2. Include archon-4 and archon-5 into the source tree.
3. Document functionality and parameters into the wiki.

What functionality is missing?
Huffman encoding of the alphabet.

Why is it so important to have it?
Uniformly distribute codes in the input sequence. Maximizes the comparison 
sorting productivity.

What are the implementation stages:
1. Research Huffman codes
2. Implement in a separate utility
3. Port to the main program

What functionality is missing?
Variable-size data type for sorting.

Why is it so important to have it?
Can take less memory and use limited cache more efficiently.

What are the implementation stages:
1. Implement Key class
2. Fix key packing procedure
3. Use proper template types

What functionality is missing?
Induce() function can be rewritten to benefit from small alphabets.

Why is it so important to have it?
Better performance in the heaviest use cases: the first iteration always has a 
small alphabet.

What functionality is missing?
Inverse BWT to check the correctness of the output.

What is the benefit of implementing the support for it?
It's a proof all the complex algorithm stages work together correctly.

What are the implementation stages:
1. Write Boo code for it
2. Research possible GPU implementation

What functionality is missing?
Configurable radix depth and key length.

Why is it so important to have it?
To evaluate the cost of improvements.

What are the implementation stages:
1. Add radix depth parameter.
2. Create a configuration notion.
3. Add command-line options.
4. Verify different configurations to work.