Page 3 of 13 FirstFirst 12345 ... LastLast
Results 61 to 90 of 364

Thread: bsc, new block sorting compressor

  1. #61
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    1024mb block isn't available in 32-bit version

  2. #62
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    Such 2 GB limit for memory block allocation extists even under 64-bit Windows.

  3. #63
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    only for 32-bit programs

  4. #64
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    Look carefully, I'm not talking about total memory available for the program, but single memory block allocation...

  5. #65
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    for example 64-bit lzma allocates up to 8gb in single block

  6. #66
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts

    Wink

    Try for yourself!

  7. #67
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    Code:
    #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
    Last edited by Bulat Ziganshin; 2nd June 2010 at 11:16.

  8. #68
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    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

  9. #69
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,897
    Thanks
    291
    Thanked 1,267 Times in 715 Posts
    > 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.

  10. #70
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    Quote Originally Posted by encode View Post
    Probably the catch in size_t
    yes, sizeof(int)==4 even on x86-64. size_t==unsigned long long

  11. #71
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts
    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.

  12. #72
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    So, Bulat, try something like this:
    Code:
    int *ptr=(int *)malloc(0xC0000000);
    if (!ptr)
      printf("Failed!\n");
    free(ptr);

  13. #73
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    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

  14. #74
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by encode View Post
    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?
    Code:
    void * bsc_malloc(size_t size)
    {
      #if defined(WIN32) || defined(WIN64)
          return VirtualAlloc(0, size, MEM_COMMIT, PAGE_READWRITE);
      #else
          return malloc(size);
      #endif
    }
    Enjoy coding, enjoy life!

  15. #75
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Bulat Ziganshin View Post
    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.
    Enjoy coding, enjoy life!

  16. #76
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    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
    Last edited by inikep; 7th June 2010 at 12:04.

  17. #77
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    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

  18. #78
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    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...

  19. #79
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Quote Originally Posted by encode View Post
    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.

  20. #80
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    Quote Originally Posted by encode View Post
    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

  21. #81
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by inikep View Post
    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..
    Enjoy coding, enjoy life!

  22. #82
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    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...

  23. #83
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,010
    Thanks
    399
    Thanked 398 Times in 152 Posts
    inilep, can you send me that weird binary files? (e.g. DCT coefs)

  24. #84
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Bulat Ziganshin View Post
    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.
    Enjoy coding, enjoy life!

  25. #85
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Quote Originally Posted by encode View Post
    inilep, can you send me that weird binary files? (e.g. DCT coefs)
    Already sent by e-mail

  26. #86
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,562
    Thanks
    772
    Thanked 687 Times in 372 Posts
    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?

  27. #87
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by Bulat Ziganshin View Post
    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.
    Enjoy coding, enjoy life!

  28. #88
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    412
    Thanks
    38
    Thanked 64 Times in 38 Posts
    @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

  29. #89
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post
    Quote Originally Posted by joerg View Post
    @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.
    Last edited by Gribok; 15th June 2010 at 01:21.
    Enjoy coding, enjoy life!

  30. #90
    Programmer Gribok's Avatar
    Join Date
    Apr 2007
    Location
    USA
    Posts
    159
    Thanks
    0
    Thanked 2 Times in 1 Post

    bsc version 2.2.0

    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
    Enjoy coding, enjoy life!

Page 3 of 13 FirstFirst 12345 ... LastLast

Similar Threads

  1. Brute forcing Delta block size
    By SvenBent in forum Data Compression
    Replies: 2
    Last Post: 2nd May 2009, 12:44
  2. Block sorting for LZ compression
    By Bulat Ziganshin in forum Forum Archive
    Replies: 15
    Last Post: 14th April 2007, 15:37

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •