Tree alpha v0.1 download

[Piotr Tarsa]

I tried time but only got 1 second resolution. Is that normal?

It seems so, unfortunately. http://www.cplusplus.com/reference/ctime/time_t/ says:

type time_t <ctime>
Time type
Alias of a fundamental arithmetic type capable of representing times, as those returned by function time.

For historical reasons, it is generally implemented as an integral value representing the number of seconds elapsed since 00:00 hours, Jan 1, 1970 UTC (i.e., a unix timestamp). Although libraries may implement this type using alternative time representations.

Portable programs should not use values of this type directly, but always rely on calls to elements of the standard library to translate them to portable types.

On the other hand, function 'clock_gettime' suggested by user 'algorithm' seems to be working on my system. I've implemented a program using documentation at https://linux.die.net/man/3/clock_gettime and snippet from https://gist.github.com/diabloneo/9619917 .

Example code ( https://ideone.com/6XcQ7d ):

#define _POSIX_C_SOURCE 199309L

 

#include <stdio.h>

#include <time.h>

#include <unistd.h>

 

void timespec_diff(const struct timespec * start, const struct timespec *stop,

                   struct timespec *result) {

    if ((stop->tv_nsec - start->tv_nsec) < 0) {

        result->tv_sec = stop->tv_sec - start->tv_sec - 1;

        result->tv_nsec = stop->tv_nsec - start->tv_nsec + 1000000000;

    } else {

        result->tv_sec = stop->tv_sec - start->tv_sec;

        result->tv_nsec = stop->tv_nsec - start->tv_nsec;

    }

    return;

}

 

void timespec_print(const char * description,

                    const struct timespec *start, const struct timespec *stop) {

    struct timespec result;

    timespec_diff(start, stop, &result);

    double seconds = result.tv_sec + result.tv_nsec / 1e9;

    printf("times elapsed for clock '%s': %lf\n", description, seconds);

	return;

}

 

int main(void) {

	struct timespec start_clock_realtime;

	struct timespec start_clock_monotonic;

	struct timespec start_clock_process_cputime_id;

	struct timespec start_clock_thread_cputime_id;

 

	struct timespec finish_clock_realtime;

	struct timespec finish_clock_monotonic;

	struct timespec finish_clock_process_cputime_id;

	struct timespec finish_clock_thread_cputime_id;

 

	clock_gettime(CLOCK_REALTIME, &start_clock_realtime);

	clock_gettime(CLOCK_MONOTONIC, &start_clock_monotonic);

	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_clock_process_cputime_id);

	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start_clock_thread_cputime_id);

 

	sleep(3); // seconds

 

	clock_gettime(CLOCK_REALTIME, &finish_clock_realtime);

	clock_gettime(CLOCK_MONOTONIC, &finish_clock_monotonic);

	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &finish_clock_process_cputime_id);

	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &finish_clock_thread_cputime_id);

 

	timespec_print("realtime", 

		&start_clock_realtime, &finish_clock_realtime);

	timespec_print("monotonic",

		&start_clock_monotonic, &finish_clock_monotonic);

	timespec_print("process cputime id",

		&start_clock_process_cputime_id, &finish_clock_process_cputime_id);

	timespec_print("thread cputime id",

		&start_clock_thread_cputime_id, &finish_clock_thread_cputime_id);

 

	return 0;

}

 

Result:

times elapsed for clock 'realtime': 3.000057
times elapsed for clock 'monotonic': 3.000057
times elapsed for clock 'process cputime id': 0.000007
times elapsed for clock 'thread cputime id': 0.000007

Precision seems to be pretty good. Check if your compiler gives similiar results (I hope so).

[Kennon Conrad]

Yes, I get similar results. I still don't understand why my compiles give global time for clock(), but I guess that mystery will remain unsolved. I agree precision is pretty good, much better than with clock.

I am curious though about one thing you did that I didn't do in post #835:

double seconds = result.tv_sec + result.tv_nsec / 1e9;

Will compilers always convert result.tv_nsec and 1e9 to double before doing the divide?

[Bulat Ziganshin]

1e9 is a constant of double type, arith operators promote narrower operand to a wider one before calculation

[Kennon Conrad]

I changed a few things for the "fast" mode (-f) and got faster compression than I ever expected. The printing of elapsed time has been fixed too.

GLZA c -f enwik8 enwik8.glza

Compressed 100000000 bytes -> 20722473 bytes (1.6578 bpB) in 24.142 seconds.

GLZA c -f enwik9 enwik9.glza

Compressed 1000000000 bytes -> 167188835 bytes (1.3375 bpB) in 556.622 seconds.

GLZA c -f Silesia.tar Silesia.tar.glza

Compressed 211957760 bytes -> 51559957 bytes (1.9460 bpB) in 132.188 seconds.

[algorithm]

Maybe silesia.tar has low compression ratio because GLZA is not good for non uniform files?Does it remove symbols from the dictionary?

[Kennon Conrad]

Maybe silesia.tar has low compression ratio because GLZA is not good for non uniform files?Does it remove symbols from the dictionary?

Yes, GLZA is not as effective for non-uniform files as for uniform files. It seems to also generally not be as effective as LZMA for files that are not text-like. GLZA does remove low frequency symbols from the dictionary but this is likely an area that could be improved. Here's a plot of the dictionary size vs. file position for Silesia.tar. In total, there are 1,525,516 dictionary entries, but most come and go:

[Kennon Conrad]

Here is GLZA version 0.10. The main goal for this version was to simplify the code and improve decompression speed.

Functionally, the "-f" flag (faster compression) is now the default and "-x" flag (extreme compression) can be used to get the previous default slower but usually better compression.

The convoluted multi-mtf queue scheme that could hold up to 1152 symbols has been replaced by a single queue holding up to 256 symbols. To reduce the number of symbol moves between the mtf queue and the dictionary a new signal type has been added that tells the decoder whether or not to put an mtf eligible symbol into the queue. So now symbols never fall out of the mtf queue (without being used) and queue shuffling associated with queue misses is gone. The side benefit is that the queue can be smaller, making less overhead for queue hits and also giving lower average queue positions. The complication is that now the code has to figure out which symbols to put in the queue. This is not so easy, I think the code could be better but it's the best I could do for now.

There were quite a few changes to simplify the code, too many to remember them all, and a few bug fixes including one that may have affected Gonzalo earlier. The overall results are that compression and decoding are (a little) faster and encoding is slower. Test results for enwik9 show a decompression speed improvement of about 15% and a compression improvement of almost 1 MB, putting it at #20 on LTCB, something that has been a goal of mine for quite a while:

enwik9:

GLZA c enwik9 enwik9.glza:  167,832,309 bytes in 594 seconds, 7452 MB RAM.
GLZA d enwik9.glza enwik9:  12.1 seconds, 355 MB RAM.

GLZA c -x -p3 enwik9 enwik9.glza:  163,768,203 bytes in 8184 seconds, 8205 MB RAM
GLZA d enwik9.glza enwik9:  12.2 seconds, 429 MB RAM.

enwik8:

GLZA c enwik8 enwik8.glza:  20,753,713 bytes in 25.9 seconds, 952 MB RAM.
GLZA d enwik8.glza enwik8:  1.35 seconds, 47 MB RAM.

GLZA c -x -p3 enwik8 enwik8.glza:  20,356,097 bytes in 420 seconds, 2140 MB RAM
GLZA d enwik8.glza enwik8:  1.40 seconds, 57 MB RAM.

A .zip file of the source code is 69,980 bytes.

If anyone has any problems, please let me know.

[Kennon Conrad]

I didn't realize until after the latest release that one of the 4 byte fields in the dictionary entry structure wasn't really necessary so I took it out and got about 2% faster decompression and 3 - 4% less RAM usage when decompressing enwik9 (I did not rerun the compression from v0.10):

enwik9:

GLZA c enwik9 enwik9.glza:  167,832,309 bytes in 594 seconds, 7452 MB RAM.
GLZA d enwik9.glza enwik9:  11.9 seconds, 344 MB RAM.

GLZA c -x -p3 enwik9 enwik9.glza:  163,768,203 bytes in 8184 seconds, 8205 MB RAM
GLZA d enwik9.glza enwik9:  11.9 seconds, 413 MB RAM.

enwik8:

GLZA c enwik8 enwik8.glza:  20,753,713 bytes in 25.9 seconds, 952 MB RAM.
GLZA d enwik8.glza enwik8:  1.30 seconds, 45 MB RAM.

GLZA c -x -p3 enwik8 enwik8.glza:  20,356,097 bytes in 420 seconds, 2140 MB RAM
GLZA d enwik8.glza enwik8:  1.36 seconds, 54 MB RAM.

A .zip file of the source code is now 69,935 bytes.

[Kennon Conrad]

Here is a new version of GLZA, version 0.11. It's the same basic idea but there are lots of changes, including the following highlights:

GLZAcompress:
Added an order 1 trailing character/leading character deduplication candidate scoring formula. This can be used by providing a "-o1.0" command line option. Without this option, it will use the order 0 score formula. Values between 0.0 and 1.0 will use a blend of the two candidate score formulas. Using the -o option forces extreme (-x) compression mode. Using the -o option slows down compression, maybe 50% on average. Overall, I'd say order 1 and order 0 typically provide similar compression ratios, order 0 creating a typically smaller grammar but order 1 creating a grammar that is slightly more predictable with an order 1 model. On the files I tested, on average -o0.5 worked a little better than -o0.0 or -o1.0.
Increased the maximum input file size from 2 GB to almost 4 GB. I didn't test this much at all. User beware, it may not work and you better have a lot of RAM (up to 64 GB) and time, especially if you are using the -x or -o options.

GLZAencode:
Added additional models and blending of model predictions. It's probably not the best implementation but does generally improve the compression ratio a little.
Simplified the selective MTF queue selection code and made it generally more effective.
For capital encoded files, changed the MTF queue to three queues, one for symbols that start with a space character, one for symbols that start with an alphabet (a - z) character, and one for the rest of the symbols and added a field to indicate with queue the next symbol is coming out of (unless the most recent trailing character was a capital encode character, in which case it goes straight to the a - z queue.

GLZAdecode:
Modified the code to support GLZAencode changes.
Changed the dictionary structure from a set of indexes into an array of dictionary structures per starting symbol/code length combination to a set of arrays of dictionary structures per starting symbol/code length combination. Now the code has to move dictionary structure data into and out of the mtf queue but it doesn't use as much RAM and the dictionary data can be accessed more directly.

Results for enwik8/9 are below, with options -o0.6, -p4, -r20000 giving the best compression ratios of the combinations I tested. The "-x -p3" option is shown for comparison to the previous version.

enwik9:

GLZA c -o0.6 -p4 -r20000 enwik9 enwik9.glza:  161,966,886 bytes, 17,031 seconds, 13,071 MB RAM
GLZA d enwik9.glza enwik9:  9.9 seconds, 384 MB RAM

GLZA c -x -p3 enwik9 enwik9.glza:  162,899,155 bytes, 8219 seconds, 8220 MB RAM
GLZA d enwik9.glza enwik9:  9.9 seconds, 383 MB RAM

GLZA c enwik9 enwik9.glza:  166,844,914 bytes, 593 seconds, 7463 MB RAM
GLZA d enwik9.glza enwik9:  10.1 seconds, 327 MB RAM

enwik8:

GLZA c -o0.6 -p4 -r20000 enwik8 enwik8.glza: 20,114,673 bytes, 782 seconds, 2347 MB RAM
GLZA d enwik8.glza enwik8: 1.24 seconds, 50 MB RAM

GLZA c -x -p3 enwik8 enwik8.glza: 20,247,308 bytes, 423 seconds, 2142 MB RAM
GLZA d enwik8.glza enwik8: 1.23 seconds, 50 MB RAM

GLZA c enwik8 enwik8.glza: 20,636,657 bytes, 25.4 seconds, 954 MB RAM
GLZA d enwik8.glza enwik8: 1.22 seconds, 43 MB RAM

A .zip file of the source code is 75,527 bytes.

[Shelwien]

Getting heap corruption crash when trying to encode this file, zero output.
"GLZA.exe c 00270.6 1"

[Kennon Conrad]

Getting heap corruption crash when trying to encode this file, zero output.
"GLZA.exe c 00270.6 1"

Thank you for the error report. There was a bug in the encoder.

[dot]

Getting an error:

$ ./glza-v0.11.1/GLZA c 1_42_polytope_7-cube.svg 1_42_polytope_7-cube.svg.glza
Applying 60 byte delta transformation
cap encoded: 0, UTF8 compliant 0
Found 29344554 symbols
double free or corruption (out)43887 grammar rules
Aborted

Regards
Dot

If it's of any use:
Debian 10 Testing amd64
gcc (Debian 9.2.1-21) 9.2.1 20191130
OR clang version 9.0.0-4 (both produce the same error)
libc6 2.29-3

[Shelwien]

I tested this file with windows exe from GLZA_v0.11.1.zip - it crashes:

Z:\008>GLZA.exe c 1_42_polytope_7-cube.svg 1b
Applying 60 byte delta transformation
cap encoded: 0, UTF8 compliant 0
Found 29344554 symbols
PASS 23: grammar size 1487309, 44198 grammar rules

"GLZA.exe c -x 1_42_polytope_7-cube.svg 1" works though.

[Kennon Conrad]

Thank you for the error report. The default fast compression option had a bug in the list management when removing overlapping deduplication candidates. This is fixed now. Now it gives 1144182 bytes for the compressed file, 0.3119 bpB. Using the -x option gives 0.2860 bpB.

[Self_Recursive_Data]

Kennon, very nice compressor! Wow!! So can you explain to me very clear and in few words exactly (mostly) how it works so that I can replicate your algorithm. I read the pdf... I see you are looking for the best longest phrases like Byte Pair Encoding when you mention "954 characters. It appears 1694 times in the encoded file". What encoded file? You mean wiki9 don't you? Or by encoded you mean the tree holding wiki9 lol?

1) So you build a tree, a trie ? (Of all of wiki9). See figure_1 below.
2) Are you finding the common "codes" in wiki9 by a form of Byte Pair Encoding ? Ex. "[but afterwards][ the][ cat][ was in the ][box]".
3) And are you replacing these windows (where they sit in wiki9, like Huffman does) with their own "huffman-like" code ? Ex. "[10100000][1001][0100][101110011][010]".
4) Can you explain the "best code" discovery again? So you look for what in the tree/trie? A node that extends very long and has few children for miles? Or also is frequent? Or is near the Root?

Figure_1 (tree):
//////////a<
////a<
//////////b<
S<
//////////a<
​////b<
//////////b<