Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #3174

Re: How many additions in fastest DCT ?

Show all headers | View raw

On 9/15/2015 2:22 AM, James Dow Allen wrote:
> BGB <cr88192@hotmail.com> might have writ, in news:mt6o1q$hc1$1
> @news.albasani.net:
>
>> bitstream/VLC backend, leading to a coder which has its execution time
>> dominated by the VLC and entropy coding...
>
> The ballpark time allocation for my high-speed Jpeg decompressor IIRC was
> about 52% color-space conversion and replication, 35% DCT, 12% Huffman.
> The Huffman decoder was driven by a largish table.
>

in my JPEG decoders, colorspace conversion and Huffman/VLC tended to 
dominate, with DCT in 3rd place.

on my PC, I have gotten JPEG decoders up to around 90 Mpix/sec, which 
falls just short of XviD, and is notably faster than Theora (I was 
generally testing its use for MJPEG coded video-clips).

if multiple decoding threads are used, then JPEG decoding can go at 
around 300 Mpix/sec.


I have yet to beat out XviD on a performance-front with DCT based 
designs (they seem to have some sort of "secret sauce" that makes its 
decoding fast, but only if quality isn't maxed out, where its decode 
speed seems to go in the toilet).

my VQ based designs tends to be somewhat faster though.

though worth noting is that my PC isn't particularly new or fast.



but, I was writing about was this experimental design:
http://cr88192.mooo.com:8080/wiki/index.php/BTIC2D

where performance suffers pretty hard in the entropy/VLC step (which is 
based on Adaptive-Rice codes), causing it to dominate the overall 
performance.


I suspect it is due to several factors:
   need to write out zero-runs and values as separate symbols;
   decoding a symbol requires multiple bitstream reads (*);
   ...

it also seems that zero-runs tend to be much rarer and shorter than with 
larger blocks.

*: currently, one read per 8 bits of Q-value, and another read for the 
N-bit suffix.

moving to an 8x8 block and Huffman coding should hopefully permit higher 
speeds.

however, Huffman complicates use of incremental coding and sending spans 
of coded blocks via UDP. this is how video streaming works in my robot 
projects, the video stream is basically a mass of UDP packets hitting 
the receiver and being decoded/displayed as they arrive, provided they 
have a higher frame-number than the blocks currently displayed in that 
location.

generally, you want each UDP datagram to be independent of the preceding 
packets. with Huffman coding, there is the requirement that the decoder 
also have the appropriate table, which is a problem if the datagram with 
the table is dropped or arrives later than the image datagrams.

though, granted, one could use primarily fixed tables to sidestep this 
issue.


> I've always enjoyed micro-optimizing code and came up with assembly
> language routines for both Intel-386 and Motorola 68020. Because of my
> fetish for extreme micro-optimzation, I ended up with different approaches
> for the two processors!  (A main difference is how those two machines
> handle shift counts greater than 31.)  Unfortunately I no longer have the
> assembly code, but I'll send you a C-language version of my Huffman decoder
> if you wish.
>

my Huffman decoder is usually ok, as can be noted, I was having 
performance problems with a Rice-coding based design, not a Huffman 
based design.


generally it works like this:
peek 16 bits;
use high 8 bits to index a table;
if Length<=8:
   skip L bits and return the symbol;
otherwise:
   iterate the symbols with this prefix;
   skip L bits and return matching symbol.

while a 16 bit table could do it all at once, my experience is that 12 
and 16 bit tables tend to make performance suffer (I suspect due to too 
much cache pressure).

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 08:54 +0000
  Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 11:30 +0200
    Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 11:40 +0000
      Re: How many additions in fastest DCT ? jdallen2000@yahoo.com - 2015-09-14 05:53 -0700
      Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 21:29 +0200
        Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:08 +0000
          Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:08 +0200
          Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-15 14:17 +0000
    Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-14 10:05 -0500
      Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:22 +0000
        Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:14 +0200
          Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 09:16 -0500
        Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 08:41 -0500
    Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-14 20:59 +0000
  Re: How many additions in fastest DCT ? Phil Carmody <pc+usenet@asdf.org> - 2015-11-18 21:51 +0200

csiph-web