bsc, new block sorting compressor

[Bulat Ziganshin]

1024mb block isn't available in 32-bit version

[encode]

Such 2 GB limit for memory block allocation extists even under 64-bit Windows.

[Bulat Ziganshin]

only for 32-bit programs

[encode]

Look carefully, I'm not talking about total memory available for the program, but single memory block allocation...

[Bulat Ziganshin]

for example 64-bit lzma allocates up to 8gb in single block

[encode]

Try for yourself!

[Bulat Ziganshin]

#include <stdio.h>
#include <stdlib.h>
int main()
{
  printf("%p",malloc(size_t(3)<<30));
}

C:\!\FreeArchiver\!>compile-msvc64.cmd malloc3g.cpp
Setting environment for using Microsoft Visual Studio 2008 Beta2 x64 tools.
Microsoft (R) C/C++ Optimizing Compiler Version 15.00.30729.01 for x64
Copyright (C) Microsoft Corporation. All rights reserved.

malloc3g.cpp
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation. All rights reserved.

/out:malloc3g.exe
malloc3g.obj
Elapsed time = 0.172 seconds



C:\!\FreeArchiver\!>malloc3g.exe
000000007FFF0040

[encode]

Waiting for Shelwien...

Well, working under BCM v0.10 64-bit I was unable to allocate more than (2<<30)-1 bytes. The compiler is Visual Studio 2008 Pro...

Probably the catch in size_t

[Shelwien]

> Waiting for Shelwien...

Erm, what?..

Anyway, there could be differences in VS versions.
Using VirtualAlloc instead of malloc might be more certain way to check it.

[Bulat Ziganshin]

Probably the catch in size_t

yes, sizeof(int)==4 even on x86-64. size_t==unsigned long long

[willvarfar]

Shifting is one of the things that bit me when migrating to 64bit.

int and unsigned are 32-bits even on x86 compilers.

numeric literals in code, unless explicitly suffixed by a type such as L for "long" are int

So malloc(3 << 30) is asking the compiler to generate code to take a 32-bit value (3) and shift it 30 places, which still makes the result 32-bit (losing the high bits).

That's why there's a type on the literal in the code Bulat posted.

But certainly in on x86 you can have individual allocations up to - I'm not sure what the limit is, but its terrabytes. And you don't need physical RAM to back up that allocation, the malloc is reserving the address space not committing the pages.

[encode]

So, Bulat, try something like this:

int *ptr=(int *)malloc(0xC0000000);
if (!ptr)
  printf("Failed!\n");
free(ptr);

[Bulat Ziganshin]

0xC0000000ll will work for any numbers. but dealing with numbers is general C topic, don't mix this with max block allocated by malloc/OS

[Gribok]

And can you please explain how you are able to use 1 GB block with libdivsufsort! Max allocation block is 2 GB = 512 M int elements... What kind of trick do you use? Do you use divbwt() for BWT construction, if so, is divbwt() able to deal with 1 GB block, or you use divsufsort() for suffix array construction?

void * bsc_malloc(size_t size)
{
  #if defined(WIN32) || defined(WIN64)
      return VirtualAlloc(0, size, MEM_COMMIT, PAGE_READWRITE);
  #else
      return malloc(size);
  #endif
}

[Gribok]

Ilya, can you please technically explain changes in two last versions?

Major changes:
1. Changed blocks synchronization in bsc.cpp. So now blocks are saved to output file ASAP after compression/decompression. Blocks order are unpredictable, so for correct decompression additional information like block offset is saved to output. This works about 5% faster in Quad-core CPU.
2. New function is added to parallel driver for qlfc. Previously I divide BWT/ST to equal parts before QLFC. But this gives not 100% CPU utilization. So now I am using some heuristics which give me 5-10% if compressing file as single block.
3. New segmentation function. Better segmentation.

[inikep]

Ilya thanks for the amazing compressor!

BBB has very slow sorting, but also has a very good CM-compressor after a ST/BWT stage (results similar to BCM).
Ilya can you add to BSC the best compression option based on a CM-compressor from BBB?

BBB sources:
http://mattmahoney.net/dc/text.html#1640

[Bulat Ziganshin]

bwt.cpp:
int index = divbwt(T, T, NULL, n, features && LIBBSC_FEATURE_MULTITHREADING);

should use "&" instead of "&&". i think it's reason of using >100% of cpu in -T mode

[encode]

BCM ls both stronger and faster than BBB! IMHO, BBB has very inefficient CM. BCM proofs that, the new, upcomming version will show even more extreme performance advantage. Although, BCM is, and wil be closed-source project...

[inikep]

BCM ls both stronger and faster than BBB! IMHO, BBB has very inefficient CM. BCM proofs that, the new, upcomming version will show even more extreme performance advantage. Although, BCM is, and wil be closed-source project...

On binary data I'm working with (e.g. DCT coefficients) BBB is slightly better than BCM and much better than BSC.

[Bulat Ziganshin]

BCM ls both stronger and faster than BBB! IMHO, BBB has very inefficient CM. BCM proofs that, the new, upcomming version will show even more extreme performance advantage. Although, BCM is, and wil be closed-source project...

there are lot of interesting closed-source project but i don't think that any of them is more useful than BBB when one want to learn bwt+cm

[Gribok]

On binary data I'm working with (e.g. DCT coefficients) BBB is slightly better than BCM and much better than BSC.

Try to use some filers before compression, this may improve speed and compression ratio. Also you could try different sorting algorithms like ST and change contexts order. bsc usually working very well on data with strong contexts like text, xml, source..

[encode]

BTW, BCM 0.10 probably is the weakest of all BCMs. Espesially it's bad at binaries. With the new v0.11 I solved that issue...

[encode]

inilep, can you send me that weird binary files? (e.g. DCT coefs)

[Gribok]

bwt.cpp:
int index = divbwt(T, T, NULL, n, features && LIBBSC_FEATURE_MULTITHREADING);

should use "&" instead of "&&". i think it's reason of using >100% of cpu in -T mode

Nice catch. This is a bug. Source code is updated.

Note: "-t" != disable multi-threading. But I can add such option to disable multi-threading if some one interested in.

[inikep]

inilep, can you send me that weird binary files? (e.g. DCT coefs)

Already sent by e-mail

[Bulat Ziganshin]

i personally interested to have 2 options: to disable parallel block processing (but keep intra-block parallelism) and to disable m/t completely. just to research perfromance

also, you don't answered about my m/t unbwt idea. is it possible?

[Gribok]

i personally interested to have 2 options: to disable parallel block processing (but keep intra-block parallelism) and to disable m/t completely. just to research perfromance

also, you don't answered about my m/t unbwt idea. is it possible?

It is possible, theoretically.

[joerg]

@gribok: Excuse me, but do you reading this forum: http://encode.su/threads/456-zpaq-updates/page4 ?

ask: would it be possible within zpaq to implement such a compression-method like ST5 from the new bsc 2.1.5 ?
Matt Mahoney wrote: It would be possible to write a ST5 postprocessor as well. I probably won't because it is patented in the U.S.

@gribok: i can not understand - how can such thing patented in the U.S. - if it is open source (GPL) as it is written in source of bsc ?

best regards

[Gribok]

@gribok: Excuse me, but do you reading this forum: http://encode.su/threads/456-zpaq-updates/page4 ?

ask: would it be possible within zpaq to implement such a compression-method like ST5 from the new bsc 2.1.5 ?
Matt Mahoney wrote: It would be possible to write a ST5 postprocessor as well. I probably won't because it is patented in the U.S.

@gribok: i can not understand - how can such thing patented in the U.S. - if it is open source (GPL) as it is written in source of bsc ?

best regards

Yes, Sort or Schindler Transform is patented by US patent 6,199,064. And I do not know if nonprofit and open source implementation violates patent rules. I would appreciate if someone can clarify this to me. If this a violation I will remove it from bsc.

Note: I send email to Michael Schindler, but office@compressconsult.com and szip@compressconsult.com seam to me is not working.

[Gribok]

New version 2.2.0 is available for testing:

[+]: Parallel version of reverse BWT transform.
[+]: Parallel version of forward ST transform(max 2 cores).

Note: This version is not compatible with previous one.

You can download new version from my web site http://libbsc.com/default.aspx