Results 1 to 10 of 10

Thread: Huffman on GPU

  1. #1
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,491
    Thanks
    730
    Thanked 655 Times in 351 Posts

    Huffman on GPU

    While very slow, it may be interesting: http://habrahabr.ru/blogs/hi/124210/

    Another, faster implementation: https://github.com/Kentzo/phuffman, "cuda" branch (the say that it's 20% faster than fast ari = www.cipr.rpi.edu/~said/FastAC.html )

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,047
    Thanks
    166
    Thanked 876 Times in 439 Posts
    Comparing C/GPU vs C#/CPU on compression algos - that's really fresh imho.
    10MB/s static huffman becomes fast.
    Java would be better though - I've seen many reports that native java on linux works faster than C++ windows exe under wine.
    Still not sure whether wine is that slow, process time is that wrong, some java engine stays after program quits to finish the cached
    writes, or something else.

  3. #3
    Member Surfer's Avatar
    Join Date
    Mar 2009
    Location
    oren
    Posts
    203
    Thanks
    18
    Thanked 7 Times in 1 Post
    AFAIK java is slower than C#.

  4. #4
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Surfer View Post
    AFAIK java is slower than C#.
    On Linux? Definitely no.
    On Windows? I'd like to see a pointer to some good benchmarks, I haven't seen any yet.

  5. #5
    Member Surfer's Avatar
    Join Date
    Mar 2009
    Location
    oren
    Posts
    203
    Thanks
    18
    Thanked 7 Times in 1 Post
    Quote Originally Posted by m^2 View Post
    On Linux? Definitely no.
    No, and I think it just because Mono slower than .Net.
    Quote Originally Posted by m^2 View Post
    On Windows? I'd like to see a pointer to some good benchmarks, I haven't seen any yet.
    Yes, I've seen previously some article in russian, but can't found it now.

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,047
    Thanks
    166
    Thanked 876 Times in 439 Posts

  7. #7
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Thanks. Too bad there are so few details...I went to the site mentioned as source, but the thing is not there. No hardware info. No compiler versions. And I find it hard to believe that in a good test gcc is on average 34.8% slower than VC.
    I'm doing some comparisons right now on my filesystem benchmark. It's clearly not a general-purpose comparison, but gcc 4.5.2 beats VC8 9:2 (tied in 5 tests). In that benchmark it always lost. So while it looked really interesting at first, now I have doubts that it's reliable.

    EDIT:
    There is a mistake in the benchmark. It shows that GCC is 34.8% slower than VS, but numbers (and chart) show that it's actually faster by ~1/3.
    It looks much better now...though I would still like to know why is Java on Linux so much faster than on Windows. Was it even tested on the same box?
    Last edited by m^2; 10th October 2011 at 13:15.

  8. #8
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,468
    Thanks
    26
    Thanked 118 Times in 93 Posts
    Well, that charts shows that Java on Linux was faster than anything on Windows Bear in mind that some tested programs uses C/ C++ libraries like GMP.

    Some benchmarks like binary-trees are non representative, as C/ C++ versions use object pools but Java versions use normal allocation through 'new' operator. If we compare allocation through new and then garbage collection or manual deallocation, Java wins over C/ C++.

    If you want actual numbers, look at: http://shootout.alioth.debian.org/u6...re-fastest.php
    Today, on Linux at least, Haskell on GHC is almost as fast as C# on Mono and Lisp on SBCL is faster than both.

    Comparing the medians:
    1.05 for C
    1.08 for C++
    1.45 for warmed up Java 7
    1.70 for cold Java 7

    Overall it seems that for complex HPC Linux is the way to go (definitely not Windows) and the performance gains of C++ over Java do not offset the productivity deficits often. On the other hand Java still lacks unsigned numbers (WTF?) so for many tasks this can be too troublesome (as was in case of my QRotSort). And in case of relatively simple algorithms (eg below 100 KiB of raw C++ code) C++ is rather bearable and provides noticeable performance gains.
    Last edited by Piotr Tarsa; 10th October 2011 at 18:02.

  9. #9
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    While looking for something else, I found this CUDA/MP library for those with access to such architectures @Google code

  10. #10
    Member
    Join Date
    May 2015
    Location
    SF
    Posts
    4
    Thanks
    0
    Thanked 14 Times in 4 Posts
    I just created a huffman decoder that runs on the GPU (Metal) for iOS devices, have a look at the full source code on github: https://github.com/mdejong/MetalHuffman

  11. The Following 4 Users Say Thank You to mo_ For This Useful Post:

    boxerab (23rd December 2017),Bulat Ziganshin (23rd December 2017),Cyan (24th December 2017),Mike (23rd December 2017)

Similar Threads

  1. GPU compression again
    By Shelwien in forum Data Compression
    Replies: 13
    Last Post: 13th January 2013, 21:09
  2. CUDA/GPU-based BWT/ST4 sorting
    By inikep in forum Data Compression
    Replies: 152
    Last Post: 7th December 2011, 20:26
  3. Huffman code generator
    By Shelwien in forum Data Compression
    Replies: 2
    Last Post: 24th May 2011, 02:50
  4. huffman's Coding
    By swapy in forum Data Compression
    Replies: 5
    Last Post: 12th August 2009, 22:51
  5. Advanced Huffman Encoding
    By Simon Berger in forum Data Compression
    Replies: 28
    Last Post: 15th April 2009, 14:24

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
  •