Skybuck's Video Codec update :)
Skybuck Flying
The last couple of days I have been working on my video codec again to make
it go faster :)
Today the fruits of my labor have become apperent.
My previous huffman encoder/decoder was a generic one, a safe one and thus a
slow one.
First I figured out how to write a fast huffman decoder:
For RGB compression limiting the conceptually tree to 256 leave nodes is
enough. Since each color channel is just one byte.
So this means a "256 huffman tree" I call it: "huffman256" ;)
Using lookup tables codes can be decoded one byte at a time... instead of
one bit at a time, also no recursion required which speed it up even more,
also very few branches.
Then I made the necessary changes to the recursion algorithm for
encoding/decoding tree structure/values in one go for decoding speed of the
tree.
(I also looked at canonical huffman codes but I don't quite understand it...
and I think it has some major drawbacks for worst case scenerio's... so I
don't think it's any good at this point in time... though I might change my
mind in the future... so far I think canonical huffman is bad because at the
worst case depth the distribution bits could be immense... unless maybe
universal coding is used but this defeats it's purpose mostly. (Distrubtion
bits is related to describing the tree with a technique from microsoft
(which I saw a power presentation off) which said to specify at each depth
how many nodes there are... well at worst case depth that could be a lot ?!?
but maybe not... for 256 huffman nodes.
This requires some cool/advanced thinking... and formula's.
This is important question:
For worst case scenerio: what is the maximum ammount of nodes at each depth.
Well the answer to that question is probably for easy:
Worst case scenerio: 1 node at each depth.
So this would require only 1 bit to describe the number of nodes at each
depth.
However what about less worst case scenerio's ? and how to come up with a
formula ?
Naive but maybe a start would be:
Worst case depth: 1 bit.
Secondary worst case depth: 2 bit
Third worst case depth: 3 bit etc...
Ok back to worst case: 255 bit huffman code.
So this would lead to 255 bits at depth 1 which is ofcourse incorrect...
since at depth one there can only be two nodes...
So the big question is... how to figure out how many nodes there can be at
each depth ? (maximum case)
The answer: I don't know...
The answer to this question... might make canonical huffman codes practical
even for worst case ! ;)
Ok back to my situation.... I don't use canonical huffman codes.. but just a
normal tree structure. one bit per node.
I kept the flexible design of encoding one element at a time... via a
DecodeElement procedure... which gets called a lot in a loop.. so slight
procedure overhead... but this is probably compensated for fast loop code.
Anyway some small optimization might still be doable here... but for now it
looks pretty good.
First the red channel is decoded, then the green channel, then the red
channel.
I still need to test interleaving the channels to see if that could give
more speed ? I don't know.
For now here are the performance test results for RGB 640x480 compression
for a Call of Duty 4 image:
For 30 frames:
The old time was something like 6 to 7 seconds with the generic
HuffmanStream decoder.
Changing the generic HuffmanStream to Huffman256Stream brought down the time
to 2.5 seconds.
The new Huffman256Decoder which uses the fast table decoding brought down
the time to 0.52 seconds.
So there you have it folks ! I can now successfully and flawlessly decode:
640x480x24x30 bits in 0.52 seconds.
Let's do that calculation for kicks ;) :)
221.184.000 bits in 0.52 seconds.
27.648.000 bytes in 0.52 seconds.
(On AMD x2 3800+)
Not bad !
So that's:
425.353.846 bits in one second.
53.169.230 bytes in one second.
That's cool.
And this is just a single core, with no sse optimizations or asm or
whatever.
Just plain Delphi code :) LOL ;) =D
Yeah baby ! =D
(Also tcp was downloading a movie at 20 Kbyte/sec so not sure how much that
took away some cpu but ok ;) ).
(And some internet explorers running too but ok ;)).
So I am happy I at least outperformed the 16 MB/sec somebody else mention on
codeproject... which ran on a piii 1ghz...
I have his code too but it seemed to be limited to 32 bits which seems buggy
and there is no performance test.
I do wonder a little bit how his code would perform on my system.. I would
require a different performance test though, to make things fair. Since my
huffman256rgbdecoder goes over the input three times... for each color
channel... so his code can't even do that properly... Yeah...
I think my implementation kicks ass.. but ofcourse I am not sure because I
haven't compared it to anything else...
But do I care probably not... I have strong feeling I have good
implementation ! ;)
Now I can focus on maybe trying to multi-thread it... or maybe use special
instructions or so... so some other little optimization if possible.
But for now... it seems fast enough to do what I want.
So now... later on... I will embed/use it in my video codec to see how it
improves the speed.
And then I can start focussing on other things which need speeding up...
like probably the wheeler transform... that's probably the slowest component
right now... if I remember correctly something like 30 frames per 1.5
seconds.
So that needs to be speed up somehow... possibly multi threaded ;) Maybe I
already did that can't remember. but I am gonna look into.
Later ;),
Skybuck.
Skybuck Flying
on.
With a release version the speed is 0.50 seconds... so that's 0.02 seconds
faster ;)
Which is about 2 MB/sec faster in release mode ;) (Estimated total of 55
MB/sec)
Kinda nice too ! =D
Bye,
Skybuck ;) =D
Skybuck Flying
I however will not share the Delphi code since that's mine :)
But for processor architects seeing the assembler of the main decode routine
could be interesting... also for assembler programmers, maybe they see a way
to optimize it further:
I shall comment it a little bit to make it more clear:
// *** Begin of DecodeElement ***
00418634 53 push ebx
00418635 56 push esi
00418636 8B881C900000 mov ecx,[eax+$0000901c]
// bit position security check:
0041863C 3B8820900000 cmp ecx,[eax+$00009020]
00418642 7347 jnb $0041868b
00418644 8B9814900000 mov ebx,[eax+$00009014]
// get byte from input stream at bit position
0041864A 8BB01C900000 mov esi,[eax+$0000901c]
00418650 8BCE mov ecx,esi
00418652 83E107 and ecx,$07
00418655 C1EE03 shr esi,$03
00418658 03B018900000 add esi,[eax+$00009018]
0041865E 0FB736 movzx esi,[esi]
00418661 D3EE shr esi,cl
00418663 8BCE mov ecx,esi
00418665 80E1FF and cl,$ff
// increment bit position with 8 (will be adjusted later on)
00418668 83801C90000008 add dword ptr [eax+$0000901c],$08
// decode byte
0041866F 0FB6C9 movzx ecx,cl
00418672 8B348B mov esi,[ebx+ecx*4]
00418675 8B1E mov ebx,[esi]
// repeat if huffman code is multi-byte.
00418677 85DB test ebx,ebx
00418679 75CF jnz $0041864a
0041867B 0FB64E05 movzx ecx,[esi+$05]
0041867F 880A mov [edx],cl
// adjust bit position
00418681 0FB65604 movzx edx,[esi+$04]
00418685 29901C900000 sub [eax+$0000901c],edx
0041868B 5E pop esi
0041868C 5B pop ebx
0041868D C3 ret
// *** End of DecodeElement ***
To me it seems actually retrieving a byte out of a bit stream requires the
most instructions !
At least 9 instructions !
(Maybe it's not a problem because of memory lag ? I don't know ;))
This explains why I am interested in any new instructions which could do
this faster ?!
Also any tricks welcome ;)
Bye,
Skybuck.
Skybuck Flying
I got rid of one local variable and Delphi's compiler is able to optimize it
a little bit further:
Now it's one instruction shorter which leads to 0.48 seconds, which is 0.02
seconds faster which would mean another 2MB/sec gained just be getting rid
of one instruction ?!
So this more or less proves that every instruction counts ! ;)
004183E0 53 push ebx
004183E1 56 push esi
004183E2 8B881C900000 mov ecx,[eax+$0000901c]
004183E8 3B8820900000 cmp ecx,[eax+$00009020]
004183EE 7348 jnb $00418438
004183F0 8B9814900000 mov ebx,[eax+$00009014]
004183F6 8BB01C900000 mov esi,[eax+$0000901c]
004183FC 8BCE mov ecx,esi
004183FE 83E107 and ecx,$07
00418401 C1EE03 shr esi,$03
00418404 03B018900000 add esi,[eax+$00009018]
0041840A 0FB736 movzx esi,[esi]
0041840D D3EE shr esi,cl
0041840F 81E6FF000000 and esi,$000000ff
00418415 0FB7CE movzx ecx,si
00418418 8B348B mov esi,[ebx+ecx*4]
0041841B 83801C90000008 add dword ptr [eax+$0000901c],$08
00418422 8B1E mov ebx,[esi]
00418424 85DB test ebx,ebx
00418426 75CE jnz $004183f6
00418428 0FB64E05 movzx ecx,[esi+$05]
0041842C 880A mov [edx],cl
0041842E 0FB65604 movzx edx,[esi+$04]
00418432 29901C900000 sub [eax+$0000901c],edx
00418438 5E pop esi
00418439 5B pop ebx
0041843A C3 ret
Bye,
Skybuck.
Skybuck Flying
Storing/encoding/decoding canonical huffman codes efficiently can be done as
follows. (I won't give exact details but just a general
description/idea's/pointers, I haven't even programmed it yet but I think I
have figured it out and can do it):
So here is some theory:
A. To store the canonical huffman tree do the following:
(Optional 0). Store 1 bit to indicate if the tree exists yes/no.
1. Store the minimum depth.
2. Store the maximum depth.
3. Store the distributions at each depth. (Min depth to Max Depth)
1. How to store the minimum depth:
However the minimum depth of a tree can maximum be: 8.
So to store the minimum depth this means: 1+2+4 = 3 bits needed. (this will
assume the tree exists for at least depth 1 that's what optional 0 is for.)
So to store minimum depth: -1 (1 to 8 becomes, 0 to 7 which fits in 3 bits)
So to restore minimum depth: +1 (0 to 7 becomes, 1 to 8 which fits in a
byte/integer/variable).
So instead of using a byte for this which would be lazy ! Only 3 bits need
to be used ! So that's another 5 bits saved ;) :)
(Alternatively... maybe just use 4 bits, and get rid of optional 0, not sure
yet if that would be better;):))
2. How to store the maximum depth:
The maximum depth can be as much as 255. So here a byte/8 bits need to be
used.
3. How to store the distributions:
For a huffman tree of 256 leaves nodes this means the worst case tree/worst
case huffman code is 255 bit. (N-1).
This means the maximum number of nodes at "worst case" depths can be 256 at
most. (This is a sort of constraint)
So 8 bits per depth is maximum however we can do better here.
There is another constraint. The worst case number of total nodes:
intermediate + leave nodes is 511.
Then there is another constraint:
The number of nodes at depth 1 to 8 are fixed: 2,4,8,16,32,64,128,256.
So at lower depths lower bits can be used.
So only the depths of 9 to 255 need to be figured out.
So the first constraint there is 8 bits. It can never be more.
However this constraint is dynamic because of another constraint: 511.
So after encoding each depth, the number of minimum nodes required for the
depth can actually be subtracted from this:
"511 counter". Let's call it something like: "TotalNodesLeftForDistribution"
Determine the number of bits required for this counter. If it goes below the
8 bit constraint then it's better so simply use that.
This means the counter will go down in bits... and for practical cases this
can go quite fast.
Probably something like:
(Subtract: Distribution nodes at depth + (minimum nodes required for it -
Previous distribution Depth))
Yeah probably need to subtract the distribution number at the previous
depth, from the distribution number + required nodes for it at the current
depth ! to get an absolute minimum at each depth ;) Otherwise distributions
+ required might be counted double and that would be a bug me thinks/guesses
! ;) so this fixes it.
So this is about it.
Now everything can be stored with minimum ammount of bits possible... and
decoding/reading it use same algorithm above.
I didn't go into actually generating a canonical huffman tree.
This should be simple to do... think of it like this: Once you know how many
nodes there are at a depth... simply stuff the tree until the depths are
filled.
"Tree stuffing I shall call it" lol :)
Even a simple algorithm should then be able to figure out nice leave nodes
which can be used to encode values with.
(simply traverse the tree to find the leave nodes)
The bit length of the codes of the leave nodes should then match the bit
length of the codes of the leaves of the original huffman tree. So then it's
simply a matter of matching bit lengths from the canonical huffman tree with
the original huffman tree. To get a good translation where all
values/frequencies have exactly the same code bit length.
Now finally let's look at the savings.
My old/current approach is:
Binary Tree Structure storing. 1 bit per node.
Value storing per leave node. 8 bits per leave node.
So let's take a full balanced huffman tree as an example:
256 leave nodes + 255 intermediate nodes = 511 total nodes which means 511
bits.
However each leave node has two nulls which require two terminator bits so
that's another:
256 leave nodes * 2 = 512 bits.
256 values = 256 * 8 bits = 2048 bits.
Total 3071 bits (Maybe plus 1 for root bit not sure about that;))
So old/current situation is: 383 to 384 bytes per huffman tree.
That's quite a lot !
Now for a canonical huffman tree same situation something like the following
would be needed:
Min depth: 8 (4 bits)
Max depth: 8 (8 bits)
Distribution: 256 (8 bits)
Total: 20 bits !
So that's a major saving !
Good savings will occur for all kinds of trees.. not just this tree ! ;)
So I am now convinced canonical huffman trees can be stored very efficiently
!
It does require some more complex handling... however encoding/decoding
tree's is only a small overhead compared to actually decoding/encoding the
elements... at least that's what I think...
But my element decode routine is pretty damn fast ! so who knows ! ;)
So now I will have to do my best to implement a good/fast canonical huffman
tree encoder/decoder as well... for maximum savings.
This requires some algorithms:
I haven't thought about it thoroughly yet but my first thoughts are:
1. Depth first tree traversel to find minimum depth of tree.
2. Full tree traversel to find maximum depth of tree.
However since we have to do full tree traversal anyway these two algorithms
can simply be integrated into one:
1. Full tree traversel to find minimum and maximum depth at once.
To do this, a lookup table of worst case maximum depth is needed to keep
track of how many nodes there were at each
depth.
So that's a "DepthNodeCount" table of 255 entries containing number of nodes
at each depth counted so far.
After the full tree traversel has filled this table finding the minimum
number of nodes goes something like:
Look at first depth minimum which is 2... compare to table... if equal then
proceed... multiple with 2...
then compare, 4, 8, 16, 32, 64, 128, 256 then we done. Since minimum depth
is limited to 8.
For maximum depth proceed from minimum depth... to 255 and stop when nodes
reaches zero.
So this way finding the minimum depth and maximum depth can be done pretty
quickly !
Maybe it could even be done while building the tree. This would require
depth inversion.
The first two nodes connected together have depth 1.
Their parent will have depth 2.
And so on... until all connected to the root.
The root nodes will then indicate the maximum depth. So that's a starter...
at least the maximum depth can be calculated
during building of the tree.
To figure out the minimum depth this would require figuring out if all
leaves/left/right have all members.
This could also be calculated by keep tracking of number of nodes on each
parent.
So if left/right was set.. then number of nodes below parent is 2.
Next parent will add these previous ones together.
So that becomes 2 + 2 for balanced node... or 2 + 1 for unbalanced node or
something like.
So the node count at each parent can also indicate the minimum depth.
This would require a special boolean probably to indicate if it's still part
of the minimum depth yes or no.
Alternatively... maybe maximum depth can be used to figure out the minimum
depth to get rid of this boolean.
For example:
Calculate number of nodes for maximum depth, then subtract number of
actually nodes from this.
Then start a little loop which keeps subtracting, 2, 4, 8, 16, until it
reaches zero. this could indicate minimum depth.
Not sure if this algorithm is correct..
But such a loop sounds kind slow.. so boolean approach might be preferred.
It's not really necessary to do it while building the tree... because that
could be messy enough... so seperate algorithm/tree traversal might be nice
for a start, but could be integrated as well.. once it works ok.
Matter of taste... or speed.... ;) I will probably integrate it into the
building of the tree... since that code is pretty clean anyway, just to get
rid of extra recursions ;) <- better for speed I expect ;)
So this leaves figuring out how many nodes there are at each depth.
Actually I just realized something.
My code has two sections:
1. Building the huffman tree.
2. Building the huffman codes. (Full tree traversal)
So my code already has a full tree traversal so that can probably be used to
do all three steps:
1. Count number of nodes per depth by storing it in depth table to find
minimum depth later on.
2. Count number of nodes per depth by storing it in depth table to find
maximum depth later on.
3. Count number of nodes per depth by storing it in depth table to find
distribution per depth.
And it doesn't even require any additional extra fields ?! Wow nice !
Except ofcourse the table... and a depth counter/index for the tree
traversal !
So I was making things much more complex the necessary... hihihi.
This is nice !
So the tricky part is with the canonical huffman codes... figuring out their
exact codes hmmm.
So far I have seen one algorithm that assumes all 256 leave nodes (all N)
are encoded... but I would prefer a more flexible approach were only the
number of actual leave nodes are encoded... and so for this distribution
technique probably allows an even more flexible approach to save some more
bits.
However this could mean those algorithms seen so far are not usuable... and
my "tree stuffing idea" might have to be used... so this is something I need
to still take a look at... and I should do this first... before spending any
coding time on all these idea's because this part is crucial... if it can't
do it then everything else would have been for nothing :)
So you see I too am working at maximum efficiency :):):) lol.
Bye,
Skybuck.
Skybuck Flying
Also some further idea's I had for my codec:
It seems other codecs use something called "Motion Estimation".
From what I understand this involves taking a block of pixels of the current
frame, and searching for the best matching block in the previous frame.
Then my idea is to simply subtract these two blocks to get lower
values/codes which can compress better.
That's probably the general idea as well...
I think I already tried something like that in the past but I was only
searching for perfect matches I think...
I now think these other codecs will also use "in perfect" matches as
described above.
So this would mean:
A "vector/pointer" per block which indicates where the other best matching
block was. (Maybe even a special bit could be used to indicate if it did or
did not find any good blocks or this could simply be left out to save this
bit and just hope for the best ;)) )
So this requires some bits for a vector. Maybe something like 16 bits... 8
bits for x and 8 bits for y.
So that would limit to searching range to 256x256... something like that.
Then the differences can be encoded with huffman.
Though I wonder if motion estimation is really that effective... since
frames only change a little bit... so simply subtracting frames from each
other might more or less give the same effect...
So that's another idea for the codec... include a "subtraction" method to
see how that performs.
As always these idea's could be mixed as described with the bit but that's
overhead.
I shall "publish" one more last idea, in a new sub thread.
Bye,
Skybuck.
Skybuck Flying
Now the final idea is to somehow make it possible for the decode to try and
combine different transforms and different compression techniques all
applied to each after, after each other etc.
As a sort of multiple-round compression.
So the basic idea is:
Do multiple round compression up to a certain maximum number of rounds.
Stop prematurely if no further compression was achieved.
At each round:
Try all compression methods.
Select/keep the best one.
Compress it.
Then do another round to see if it can be compressed with anything else.
This means two kinds of compression could be done:
1. Two/three dimensional compression. 2d = frame itself, 3d=previous frame
too.
2. One dimensional compression. Try to compress the compressed output.
So this means codec could have two different kind of compression algorithm:
1. 2D/3D
2. 1D
This could require special seperation of output...
CompressionInformation.
RemainingColorInformation.
Finally transforms could be used as well.
This also means:
1. 2D/3D transforms. (Actually I haven't seen any 3D transforms yet ?! hmm
;))
2. 1D transforms.
Then the codec could be hard coded with some "paths/techniques/sequences to
try".
Such a path would be an array containing the method numbers.
(each method should have a number... maybe even a type.
So the transform/compression sequence could be something like:
TcodecOperationType =
(
// 2d transformations
cot_2d_rgb_transform,
cot_2d_peath_transform,
cot_2d_wheeler_transform,
cot_2d_bubble_to_front_transform,
// 2d compressions
cot_2d_horizontal_compression
cot_2d_vertical_compression,
cot_2d_frame_compression,
// tries them at the same time
cot_2d_horz_vert_compression
cot_2d_horz_frame_compression
cot_2d_vert_frame_compresion
cot_2d_horz_vert_frame_compression
cot_2d_motion_estimation // new
// 1d compressions to try after 2d compressions
cot_1d_wheeler_transform,
cot_1d_bubble_to_front_transform,
// work on remainining uncompressed pixels:
cot_1d_horizontal_compression (special compression which is done
after other 2d compressions)
cot_1d_vertical_compression
cot_1d_frame_compression
cot_1d_preath_prediction
// general rle compression
cot_1d_rle // general rle to work on anything.
// maybe even a mix like above
cot_1d_vert_horz_compression
cot_2d_rgb_huffman_compression,
cot_2d_universal_code_compression,
cot_1d_huffman_compression
cot_1d_universal_code_compression
cot_1d_exact_pattern_search, // winzip like/sliding windows lzx
cot_1d_pattern_estimation, // new idea, a variation of motion
estimation
// but just in 1d with inexact pattern
matching, and difference encoding
)
// an array to try out different combinations of them:
mCodecOperationSequence : array of TcodecOperationType;
Finally some of these methods might require extra parameters to specify what
there supposed to transform/compress
// alternatively they might be further split into specify domains like:
compress_compression_information_further
compress_remaining_colors_further
But maybe the parameter approach aint so bad... I don't know yet ;)
Would be nice if this was all possible to quickly try out new
transform/compression sequences.
Also for multi round support.
Finally as more cpu power becomes available... and maybe multi threaded
support is added.. then more sequences/combinations can be tried which could
find better codec sequences for certain frames ;)
So this is also a cool/nice idea which would be really nice to have for the
CODEC !! ;) =D
Bye,
Skybuck :)
Skybuck Flying
performance problem.
Instead of trying to multi-thread it... for more speed, or instead of trying
sse for more speed, a simple fix could be applied:
Instead of comparing the complete array with each other, a maximum number of
compares could be done for the comparisions.
So this is the constraint the compare function to not take to much time.
Since the problem is the compare function could take to much time when both
are equal to each other... because the compare function only stops when one
is different from the other.
As long as both are equal the comparision function will continue and
continue and continue endlessly almost it seems ;)
So to force the comparision function to quite a maximum number of compares
can be implemented.
This might make the wheeler transform less effective (?) or maybe not (?).
But it might still be good/usuable.
However I am not sure if this can work at all... because the decoder
probably assumes the complete array was sorted perfectly...
Well maybe the decoder can be adjusted a little bit to understand that that
was not the case and it was sorted up to a certain point... maybe a certain
position range or so.
So not sure if it's possible to fix it like that.
Anyway there ya go ;)
Bye,
Skybuck.
Skybuck Flying
I am not sure if it will first the rest nicely... maybe it will, maybe it
won't... time will tell.
Anyway here is the algorith/idea.
The original huffman tree is already give (as input).
All leave nodes are known... all intermediate nodes are known.
These could all be "stuffed" in a table of linked lists while they are being
counted in the table DepthNodeCount...
So DepthSiblings table could be created which has a linked list on each
entry... something efficient... nothing too complex.
Then once all siblings have been accounted for at each depth the following
happens:
The canonicalhuffman tree is constructed by starting at the bottom.
The bottom/deepest depth has leaves only... so not much to do here except
null the left/right or so...
Then proceed up the tree so to speak... so a more shallow depth.
There the number of nodes is also known... now the only thing to do is to
simply attach all siblings to these nodes.
And then proceed up the tree again to a more shallow depth...
And then simply attach those nodes to the upper nodes of the linked list.
This way the tree can be constructed pretty efficiently ?
Let's see... what's happening:
1. Full tree traversal of original huffman tree has to happen anyway.
2. Stuffing siblings in DepthSubling tree requires only a few operations,
acquire node, link node.
3. Then building the canonical huffman tree:
4. Walk all lower siblings, walk all upper siblings until all lower siblings
have been attached... proceed.
So this is pretty efficient I think..
What would be the alternative ?
Some wacky kind of recursion like algorithm... where the tree has to be
traversed everything just to insert a node somewhere...
Would a recursion routine actually be more efficient ?
Hmmm only if it could maybe be done while the original huffman is gathering
the codes. or maybe even during building the tree...
All that needs to happen is to make sure the construction of the canonical
huffman tree happens in the same way at the encoder and the decoder to make
sure the codes have the same binary values.
It probably doesn't matter where they are inserted as long as it's the same
on both sides... at least for my mentioned algorithm me thinks.
It could help to keep everything on the left side of the tree though...
Because those would then primaryly be zero's... and that could give further
compression for any other compressors that might want to go over it later
on.
It's probably not really possible to construct a canonical huffman tree
while building the tree, since it requires more or less attaching/inserting
siblings right next to each other on the same depth level... the depth level
is not really known yet while building the tree... so that would become hard
and would require swaps which is probably too much of hassle.
So that leaves the possiblity of construction it during the huffman code
traversal.
As already mentioned above... stuffing the siblings into the table can be
done here...
However is it maybe possible to stuff them directly into a canonical huffman
tree ?
I can imagine keeping track of an insertion point at each depth level or
so... but after it's been used how to proceed to the next sibling insertion
point in a tree structure... doesn't really seem that possible unless a
premade tree structure is used where all nodes are at predetermined
positions for the maximum tree... but this is probably bad idea since worst
case trees could be very strange/long.
So without wasting more time on trying to find some complex/maybe more
efficient solution I will stick to my guns and use the solution described
above for now.
Which should be nice/easy and simple and still pretty efficient to
implement.
Anyway.
The decoder assumes the tree is build from top to bottom... at least when it
comes to figuring out the constraints...
I am not sure if this will become a problem...
Probably not.. because the distribution is already given... so it can still
go ahead and figure out what the minimum requirements are for the tree to
bring down the bits per depth.
Since that's what it was all about figuring the minimum/maximum/worst case
bits to use for each level in a dynamic fashion too given certain
information and constraints.
So this actually makes it kinda easy for the decoder too.
The decoder simply builds up tables as well... then simply applies the
canonical huffman tree construction as well.
Then it can figure out the canonical huffman codes. from traversing this
tree.
However now I suddenly realize a little problem/thing I missed.
The whole concept of canonical huffman tree is to encode the entire alphabet
sort of.
So all 256 values must be encoded... otherwise the decoder will not know how
to decode a certain huffman code ?!
However this should not be much of a problem since these "empty frequencies"
nodes will just be in distribution counts as well (?)
However this raises another question:
How to include empty frequencies ? hmmm.
Maybe give them a very high frequency... to stuff them into the back of the
tree ? but this would be weird and slow things down and maybe require more
bits ?
Or maybe use a special code... for all empty frequencies.
Hmmm maybe assume all empty frequencies are in the back of the tree and then
leave them out...
Hmm strange... that can't probably work.
Maybe there is only one possible solution and that is simply give all
non-occuring items a frequency of zero/empty
and then simply build a normal huffman tree... and then turn that into a
canonicalhuffman tree...
Which is kinda what I described above... this would stuff the non-occuring
frequencies into the back of the tree.
Now the real question is how to know what was in the upper layers of the
tree ?
Any value could have been there.
This is probably where the canonical code generation plays a roll.
Maybe all these nodes need to have a steady ammount of bits more or less...
Hmmmm back to the original idea of canonical huffman codes.
The original idea was to encode the bit lengths of the canonical huffman
codes.
So encode:
0 to 255 by encoding their bitlengths.
However there bitlengths equals their depths.
So by describing how many nodes there are on each depth this reveals
something... but maybe not enough ?
Since how to know what value belongs on what depth ?
Maybe the min depth, max depth, and distribution was ment to help figure out
how many bits to use for the bitlength encoding.
Yes that could be it.
So conclusion could be:
Canonical huffman encoding requires:
MinDepth
MaxDepth
Distributions at each depth
To figure out how many bits to use for the bitlengths.
Then also output:
0 to 255's their bitlengths ?!? hmmm.
As more and more bitlength become known the number of bit required might
change but it's already pretty complex so maybe not do that for now.
I can also vaguely remember seeing something about sorting the alphabet or
something like that... maybe that has something to do with it.
Maybe sort of bitlength or sort on frequency... but then how would the
decoder know how to do that as well.. so that's a bit blury.
I could implement it really simple by using universal coding for the
bitlengths... but I don't want to do that yet... because that doubles the
ammount of bits required.
Let's see how that would be...
Assuming a full balanced huffman tree that would mean 256 leave nodes, each
have a code length of 8 bits... so universal encoding would double that to
16 bits.
Which would then mean:
256*16 bits = 4096 bits.
Which would be worse than my current situation.
So somehow a more efficient encoding has to be found.
Is it possible at all I start to wonder ;)
I did see something about a counter counting down.
Hmm... Maybe the whole idea of canonical huffman codes was not so much to
store the most efficient code in the tree...
But just a way to encode the "to-be-final" tree in the output.
So the tree in the output does not represent the final tree.
It just represents a way to build the final tree.
So this means different codes can be used for the tree in the output as long
as it can be converted to final efficient huffman codes.
Yes I think this was what it was all about.
So canonical huffman is about:
"Transforming the huffman tree, to store it more efficiently in binary form,
where the encoder and decoder can use different kinds of codes in the
"stored huffman tree"... to transform the tree from "efficient huffman
codes" to=encoder "efficient binary stored tree" back to=decoder "efficient
huffman codes".
Now the question is how to actually do it...
I seem to recall the idea of moving all nodes to the left side... so some
sort of incremental value can be obtained once known how many nodes there
are at each depth...
Yes I am starting to see it again.
Move all nodes of the original huffman tree to the left...
re-number their nodes using some sort of depth counter.
Store it in the output... then read it back in again.
However this probably requires placing "zero frequency nodes" in the huffman
tree as well ? or is this the magic of it ? by leaving it out ? hmm.
Maybe the whole idea was to use an incrementing or decrementing counter to
indicate how many bits to use to for example describe the ammount of nodes
at each depth.
The use a building tree algorithm that's the same on both sides to make sure
all values and up where they are supposed to be..
So when outputting the tree... value 0 to 255 has to be done ?
But ofcourse the tree is not like that... the values are mixed...
So maybe this is where the sorting comes into place ?
To finally sort the alphatbet back to the way it's supposed to be ?
(Or maybe exactly the opposite ? but then how would the decoder know.. so
that doesn't make much sense hmm.)
Maybe the idea is to encode the alphabet into the huffman tree... then using
the depths to describe it.
The encoder gets the same kind of alphabet... then somehow re-sort it...
based on it's depth number.
So this would "sort" the alphabet into place depending on what frequency it
had.
I think that could be it...
However still doesn't make too much sense... since the left node would
always have A,B,C,D,E etc... hmm.
Or maybe this is the trick somehow... A could be near the root on the
left... and C could be near the bottom on the right/middle of the tree...
so then A would be sorted differently then C.
So maybe the idea is not to use/stuff all nodes on the left or right or
whatever... but just let it be the way it is and then use some sort of
sorting routine to figure it out.
Like depth first sort or something like that.
Also from left to right over the siblings.
This is interesting idea I will have to explore this some further.
So this is how I think it could work very vaguely:
The min depth is given
The max depth is given.
The distribution at each depth is given. (number of nodes at each depth).
The alphabet is then simply stuffed into the tree according to the
distribution.
Maybe this is already enough to give the final huffman tree ?
Or maybe this is not enough... because this follows a regular pattern.
So then sort the tree based on depth and siblings.
This is to reveal what the alphabet was.
So to encode the alphabet properly into the huffman tree the opposite has to
happen:
The encoder has to sort the alphabet based on it's frequency.
Then the freqencies are stuff into the tree.
The decoder does the opposite:
The decoder stuffs the alphabet into the tree and then sorts the tree based
on depth first then siblings.
This will shuffle the alphabet based on the frequencies.
So this should then restore it.
Hmmm..
Bye,
Skybuck.
Skybuck Flying
I read a bit of wikipedia.
It seems the canonical version is related to fibbonicca like tree:
Maybe that's what it's all about like:
B 0
A 10
C 110
D 1110
Z 11110
E 111110
F 1111110
G 11111110
L 111111110
N 1111111110
M 11111111110
X 11111111111
(last node has 1 set)
Encoding it like that would ofcourse be inefficient that's why not the code
itself is stored but only it's bit length.
The maximum bit length can then be 255.
So this fits in 8 bits.
So 256 * 8 bits = 2048 if this simple encoding is used.
Now look what happens if it's mixed/sorted:
A 10
B 0
C 110
D 1110
E 111110
F 1111110
G 11111110
L 111111110
M 11111111110
N 1111111110
X 11111111111
Z 11110
Now imagine it as follows:
Bit lengths:
A 10000000000
B 00000000000
C 11000000000
D 11100000000
E 11111000000
F 11111100000
G 11111110000
L 11111111000
M 11111111110
N 11111111100
X 11111111111
Z 11110000000
Suppose this is the way it was stored... you could still construct the
previous tree.
However this would only give a fibbonacci tree.
So maybe here is where the trick lies.
It further more says: Make sure each canonical code has a higher value then
previous ones.
So maybe it's about encoding from the depth...
Somebody else mentioned "groups"
So a branch could be maybe seen as a group or so.
Maybe left groups versus right groups or so.
So maybe this tree is more about encoding where each of the 0 to 255 values
belong in the tree.
This ofcourse isn't so hard using normal huffman codes because that's what
they are for...
But how can it be done based on the bit length ?
Well that might only be possible by making sure each code has a unique bit
length ? or maybe a higher code ?
Hmm this is still fuzzy.
However I am starting to see a pattern.
Let's recap to my "tree stuffing algorithm"
The only thing we need to know is when to stuff which alphabet letter into
the tree.
So instead of simply stuffing alphabet 0 to 255... which would always give
the same tree...
We could simply use the bitlength of each code let decide which one is
placed/stuffed into the tree !
So there are 0 to 255 stuffings that need to take place.
So:
Stuff operation 1: take/stuff the letter with bitlength 1
Stuff operation 2: take/stuff the latter with bitlength 2.
Stuff operation 3: take/stuff the letter with bitlength 3.
Stuff operation 4: take/stuff the letter with bitlength 4.
Stuff operation 5: take/stuff the letter with bitlength 5.
Stuff operation 6: take/stuff the letter with bitlength 6.
Stuff operation 7: take/stuff the letter with bitlength 7.
So this becomes quite easy.
All we need to know is when to stuff which letter into the tree.
So the letters are re-ordered to give the correct stuffing sequence.
Re-ordering is simply done be renumbering the letters at the encoder side.
So if alphabet letter A never occured it would at the bottom... so it would
get a very long bit length like bitlength 200 or so...
So it needs to be stuffed into the tree last ;)
So I think I grasped the concept.
So this should immediatly give a little bit more efficient encoding... but
only when all alphabet letters occur in the input stream...
Can it be encoded more efficiently than 2048 bits ?
My first guess would probably be no:
Since all values needed to be encoded no matter what and there encoding can
be totally different at each step.
So there is no real way to know how to encode it more efficiently.
This is probably why some may like it...
It requires litte bit fiddling and ofcourse gives more efficient encoding
when all alphabet letters occur.
Anyway... one other idea I had to make it possible to use the best encoding
is to do it as follows:
Use a version field to indicate which version of the huffman tree is being
used.
This could for example just be one bit:
Like normal huffman tree/canonical huffman tree.
Or this version field could be "universally encoded" to allow any expansion
in the future.
Since I think there might be even a more efficient way of storing variable
huffman tree's this would be smart to do for
encoder backwards compatibility.
Well that ends my investigation into all of this... now it's time for some
code to illustrate all this canon stuff :)
Bye,
Skybuck ;)
Skybuck Flying
depth/max depth and distribution is not enough information to properly
encode/decode the tree ? (hmmm)
Bye,
Skybuck ;)
Skybuck Flying
What would happen if the alphabet is again sorted based on their canon codes
?
The indexes/letters would end up at different positions.
Now suppose that the indexes are then stuffed into the tree... this would
give a certain strange kind of tree.
Given enough information about each depth level would it be possible to
learn what index was stuffed into the tree ?
Probably not since you would have to know precisely at which leave the index
was stuffed and one simply doesn't know that.
Stuffing the indexes into the tree would simply give a balanced binary tree.
So that solves nothing.
So from whatever angle I look at it... it seems that presentation was
misleading.
I am not 100% sure but it sure seems like it... let's see if I can find it.
Actually maybe it wasn't from microsoft or maybe there was another... anyway
this one seems a bit misleading:
http://www.ensc.sfu.ca/~jiel/courses/861/pdf/03_Huffman_2.pdf
Page 43 it says:
Canonical Huffman Tree only needs:
Min, Max, Distribution.
How can that be ???
Hmm
Bye,
Skybuck.
Skybuck Flying
hoping for...
Maybe with memory requirement it means the algorithm itself...
Oh well.
Bye,
Skybuck.
Skybuck Flying
approach.
Huffman codes are decoded in an byte-lookup-table fashion/approach.
The question is:
How many tables are necessary for the worst case ?
First I thought the answer was 32 because the worst case huffman code is 255
bits, so that would mean 32 bytes.
However.... some huffman tree's could have many 9 bit codes...
So that means one table for the first 8 bits... and then many many many
tables for the second 8 bits.
Assuming 9 bits is now the new worst case the question becomes:
How many 9 bit nodes can there be ?
Let's try to reason about that instead of trying to draw a big tree ;)
The previous answer:
How many 8 bit nodes can there be was 256, with 255 nodes.
Now assuming the ammount of leaves is still 256...
How many 9 bit nodes can there be ?
Let's look at the constraint: 511 nodes total.
To make 9 bit nodes require doubling the intermediate step:
So that's 511 intermediate nodes for 512 9 bit leaves.
However there can only be 256 9 bit leaves at most.
So this means probably reduce everything by 2.
Which gives a rough estimate of: 255 tables.
Since it's probably not 256...
So that leaves one table for the first 8 bits.
So allocating 256 lookup tables should be pretty safe...
But I make no garantees that this is correct.
For now this seems ok :)
Bye,
Skybuck ;) :)
Skybuck Flying
I just implemented some basic profiling support using my own custom
linkable/scalable profiler:
Here are the total usage results from the call of duty 4 video:
VideoCodec.AdvancedVideoCodec.DeCompressor.RGBTransform: 0.98053579%
VideoCodec.AdvancedVideoCodec.DeCompressor.PaethPredictor: 20.06384212%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform: 57.14674816%
VideoCodec.AdvancedVideoCodec.DeCompressor.BubbleToFrontTransform:
7.35381206%
VideoCodec.AdvancedVideoCodec.DeCompressor.HuffmanRGB: 12.97249671%
The slowest component is now the wheeler transform ;)
So I gotta do something about that :)
Bye,
Skybuck ;)
Skybuck Flying
I just tried out the wheeler fix.
It seems to work just fine !
Hmmmm :)
Bye,
Skybuck ;)
Skybuck Flying
I tried a compare of 1000 and a compare of 100.
The compare function is only used in the encoder.
It does help a little bit for the decoder... but not that much.
Wheeler transform remains at 50 to 57% cpu usage for the decoder.
I did notice a little speed optimization that's possible:
Encoding red, green and blue occurences, might speedup the decoder a little
so it doesn't need to count those any more...
But then this could maybe be an attack vector... with unreliable data or so
;)
Oh well.
Champagne still buzzing lol :)
Bye,
Skybuck.
Skybuck Flying
I have an idea how to hopefully speed up the wheeler transform/memory access
a little bit... (or a lot?)
By "breaking the chain" ;) <- hint hint ;)
Here is a little music video to enjoy it some more :)
http://www.youtube.com/watch?v=S-W_3gVsO98&feature=related
If it works then ofcourse I will keep it secret... otherwise it's no fun ?!
:) LOL.
But I will report back on new usage/performance statistics ;)
Bye,
Skybuck =D
Skybuck Flying
Better music video link :):
http://www.youtube.com/watch?v=Zw4kM3ycdKo&watch_response
Bye,
Skybuck ;)
"Skybuck Flying" <Blood...@hotmail.com> wrote in message
news:4c0c$495dd00d$d5337e4d$32...@cache1.tilbu1.nb.home.nl...
Skybuck Flying
During the short benchmark it seems slightly faster.
But during actually codec usage it's slightly slower.
So no cookie !
Maybe the output could be sorted into place... maybe that would be faster...
but I somehow doubt it ;)
That would probably just increase memory access usage.
I still had some other idea's but those much more difficult to implement,
not yet sure if I am gonna try them ;)
Bye,
Skybuck.
Skybuck Flying
This is just one frame:
Percentages of parents:
VideoCodec.AdvancedVideoCodec.DeCompressor.RGBTransform: 0.99852239%
VideoCodec.AdvancedVideoCodec.DeCompressor.PaethPredictor: 20.41476447%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform: 57.66492693%
VideoCodec.AdvancedVideoCodec.DeCompressor.BubbleToFrontTransform:
7.07450529%
VideoCodec.AdvancedVideoCodec.DeCompressor.HuffmanRGB: 12.37339978%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode:
99.99389905%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.ResetByteCount:
0.00574242%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.CountByteValueOccurances:
4.06886601%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.DetermineBytePositions:
0.00861364%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.DetermineTransformation:
18.88719009%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.InputToOutput:
77.01343727%
Percentages of total:
VideoCodec.AdvancedVideoCodec.DeCompressor.RGBTransform: 0.99846041%
VideoCodec.AdvancedVideoCodec.DeCompressor.PaethPredictor: 20.41349712%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform: 57.66134706%
VideoCodec.AdvancedVideoCodec.DeCompressor.BubbleToFrontTransform:
7.07406610%
VideoCodec.AdvancedVideoCodec.DeCompressor.HuffmanRGB: 12.37263163%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode:
57.65782917%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.ResetByteCount:
0.00331096%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.CountByteValueOccurances:
2.34601982%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.DetermineBytePositions:
0.00496644%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.DetermineTransformation:
10.88994380%
VideoCodec.AdvancedVideoCodec.DeCompressor.WheelerTransform.Decode.InputToOutput:
44.40427610%
DeCompressTime: 0.13499733
Some interesting things can be learned from this:
The InputToOutput transformation is definetly the slowest part of the
wheeler transform as can be seen from the 77% of the time taken by the
wheeler transform. Determining the transformation array still takes a pretty
large chunk of time as well almost 20%. The reset byte count takes very
little time, as well as counting the byte occurences.
The InputToOutput is probably limited by memory access/bandwidth... so I
doubt multi-threading would give more performance ?
Maybe compacting the reds, blues and greens might give better cache usage.
The opposite could be tried as well... using integers only but that would
surely increase the bandwidth usage...
Bye,
Skybuck.
Skybuck Flying
bit.
So this deserves more experimentation and investigation ;)
Bye,
Skybuck.
Skybuck Flying
I think I made an interesting discovery... a little bit by accident... I
wanted to make a "prefetch" contest... so I wrote this little test
program...
And then I discovered that it ran very fast ?! I was like huh how can it run
that fast ?
Then I understood.
What I did was I was only decoding one channel, for example: only the red
channel... so thinking about this learned why it was so fast:
My AMD X2 processor has a secondary cache called L2 cache which is 512 KB.
So for images that are 640x480 pixels... this will fit only for one channel:
So here some numbers:
640x480x1 = 307200 bytes, *FITS*
640x480x3 = 921600 bytes, *DOES NOT FIT !!!*
So what I probably learned from this is to de-interleave the 24 bit image
first into seperate channels... and then process one channel at a time ! for
maximum caching effects ! ;)
This will require some code changes here and there... hopefully it's worth
it... I think it could be worth it... but I am not sure ;)
Actually maybe this is all bullshit... because there were at least a couple
of arrays involved.
So another explanation might be: no record field access...
Like [vIndex].Red
Maybe that's the real reason why it's so fast ?!
Or maybe even that's not the explanation...
Maybe the key chaining is just the problem ?!?!
Weird.
So I am not 100% sure why it's so fast ?! strange.
Bye,
Skybuck ;)
Skybuck Flying
Forget last post...
This time I simulated the key-ing/key-chain.
The key-chain is what makes it slow.
So that's interesting... gotta include the key-chain in the contest ;)
But I am getting tired so it will have to wait until tomorrow.
First I try to do my best at solving it...
If I really can't solve it... then I am gonna post it as a contest... for
other people to put their teeth in ;) :)
My bet for now is: I can't solve it... so this means the best thing that can
be done is pre-fetching... which requires a prefetch strategy... I am not
sure what good strategies are so this warrants a "prefetch-strategy-contest"
;) :)
Bye,
Skybuck.
Skybuck Flying
Maybe no contest.
Maybe I am already doing it optimally for the key chain... since there is
not that much choice ? hmm ;)
Bye,
Skybuck.
Skybuck Flying
Here is an idea I should try tomorrow:
The whole transformation array is an array of keys.
The primary keys just indicate where to start.
However it's not really needed to start at the primary keys.
All transformations could simply be done individually and simply write to
the output.
The only thing that's then needed later on is probably to "shift the entire
output" array to the proper location.
So to keep/say it simple:
To get the output array in the proper order/way one array copy is needed
which would go mostly sequentially...
Since maybe performing an array copy will be faster...
So this would allow all transformations to happen pretty fastly... and then
only later use the primary key to "adjust/shift/copy" the output array into
the proper location...
Like:
P = primary key
P
transformed input: |----+------
P
de-transformed output: ------|----+
Shift/copy: <<<<<<<<<<<<
result:
P
|----+------
Voila ;)
I am pretty sure this can work... I am not yet 100% sure if this will be
faster but I have a very good feeling about it ! ;) :)
Bye,
Skybuck.
Skybuck Flying
This morning I wake up to lots of snow... and I realized the idea can't work
because the transformations are chained as well and they need to be
outputted sequentially... and not randomly.
However a different idea might work.
An idea which looks a little bit like a merge sort.
The transformation array could be processed as follows:
Each transformation is copied to let's say/call it a transformation buffer.
This makes sure the start of each transformation buffer is the real
transformation.
Then for each transformation buffer, the next transformation-key-chain is
read...
And transformed behind the transformation buffer.
So first there are N transformation buffers.
Then N div 2 transformations are done. Possible in the transformation
buffers themselfes.
So the transformation buffers are merged into each other.
Then the remaining transformation buffers are merged again like N div 4.
The merging continues until all transformations buffers are merged.
This should give a correctly sequentially transformed buffer.
The only remaining problem is to make sure it's correctly shifted/put into
place at 0.
Maybe this can be done immediatly by keeping track of the primary
transformation buffer.
This would require copieing the primary one to the front all the time... not
sure if that's a good idea.. but probably not.
For now I will do the "final" copy transformation at the end to put the
array into the correct position.
This idea of merging the transformation buffers should finally work... since
it's already proven that it works for merge sort for linked lists which is
almost the same kind of chaining problem.
Except in this case... the arrays must be copied to each other to make it
sequentially... it must not be linked because that would still create a
linking-chain... that's not good... it must be done sequentially... so it's
more like a merge sort.
Except there are only two elements to look at... the first transformation of
each transformation buffer is the only thing to look at.
Once they are merged... one transformation remains... the first one.
Now there is a little other problem... how to conserve/constrain/keep the
memory requirements down.
Well again here merge sort shows "the path to the light" lol.
Merge sort uses a second array to do it's biddddding.
So the transformations can be done to a second array... which can then
function as the input array again.
This should make the algorithm really simple... and well predictable by any
memory access predicator or so.
The copieing should go fast since that's most sequentially later on...
It could even be a little bit multi threaded but then again that might give
memory access issue's and conflicts so not gonnan do that yet or not at all
;).
So for N this requires: N + N/2 + N/4 + N /8 + N/16 + N/32 + N/128 + N/256 +
N/512 + N/1024 + N/2048 + N/4096 + N/8192 + N/16K + N/32K + N/64K + N/128K +
N/256K + N/512K
So that requires roughly 19 merges... multiplied by 3 or so.
Let's calculate correct number of loops for a 640x480 picture:
round1: 307200 / 2 = 153600
round2: 153600 / 2 = 76800
round3: 76800 / 2 = 38400
round4: 38400 / 2 = 19200
round5: 19200 / 2 = 9600
round6: 9600 / 2 = 4800
round7: 4800 / 2 = 2400
round8: 2400 / 2 = 1200
round9: 1200 / 2 = 600
round10: 600 / 2 = 300
round11: 300 / 2 = 150
round12: 150 / 2 = 75
round13: 75 / 2 = 38 + 37 (problem ?! not really they will be merged into
one. take max.)
round14: 38 / 2 = 19
round15: 19 / 2 = 10
round16: 10 / 2 = 5
round17: 5 / 2 = 3
round18: 3 / 2 = 2
Round19: 2 / 2 = 1
So that's again 19 rounds... plus one extra for final copy.
Is 20 rounds per channel... so that's a total of 60 rounds for rgb.
That means
60 x 307200 bytes need to be copied per frame is: 18.432.000
This needs to happen at least 30 frames per second so that's:
18432000 x 30 = 552.960.000 bytes per second.
That's quite a lot...
I am not sure if the system/pc is able to handle so much memory.
And this is just for the wheeler transform.
It needs to do other things as well.
Hmmm.
Bye,
Skybuck ;)
Skybuck Flying
The merge sort assumes the next elements beside it can be used/sorted.
Not here with this chain.
The next key could be anywhere in the array.
And simply copieing it next to it could create doubles like so:
K1->3 K2->4 K3-7 K4->9
Which would turn into something like:
K1 K3 K3 K7.
So this would create two key 3's which would be bad.
However there is a solution to this problem... but it will probably double,
maybe even tripple the bandwidth requirements:
Solution is to swap any keys found for example:
K1 K3 K2 K4
This probably prevents multi-threading unless something very advanced is
done/used... but I am not gonna go any further with advancing it... cause
this is as far as I will take it for now.
I still wanna see what it can do so later I might give it a try ;)
Bye,
Skybuck.
Skybuck Flying
Also odd number of elements might be a problem after all... since all
transformation buffers should be linked just once.
I am not sure if it's ok to link multiples over and over... maybe that's not
bad... but what about the missing element... so that's kinda
dangerous/weird... so I am not to sure about that.
to prevent any troubles it's maybe better to use 2^n number of elements per
group.
And maybe do special processing for any remainders at each round.
To make sure all are good ? hmm.
This might prove to be a problem after all ;) gaps may not exist me
thinks... unless the algorithm can somehow detect/deal with that... oh well.
Bye,
Skybuck.
Skybuck Flying
Maybe my original idea of simply using some "loose" transformation buffers
is better...
At least these could be copied into each other when there is overlap.
So back to the original idea of transformation buffers.
Here duplicates can exist without problems.
The question is how to link them together quickly.
The solution seems simple.
Everytime a transformation buffers has found the next key... then the key is
entered into an array which points
to where the key is stored in a transformation buffer and at which position.
Then later during a next round... all transformation buffers can first check
if their start is already linked into
another transformation buffer... if so they can be merged...
However this still requires extra steps to make sure the full input array is
linked/processed, since their could be duplicates/overlaps/non processed
items.
So it could go something like this:
For each N make a transformation buffer.
Then for each N find the next key... this key is probably already somewhere
in a transformation buffer... so find
the correct transformation buffer and copy them together into one buffer.
So some transformation buffers will be merged together... will others will
not.
Then simply keep merging them together until all transformation buffers are
merged together.
Sounds simple doesn't it... but is it really this simple ?
The big question is how to do the memory allocations so they will finally
all be sequential in memory.
Each transformation buffer can't be 900 KB because that would be 900 KB x
900 KB which would mean memory explosion.
Here the idea of a secondary buffer might come in handy to copy stuff into
place sequentially/merged.
Just start with the first transformation buffer... and then as the buffer is
filled up... move the pointer forward
so that others can write there etc.
This way a new array can be made which has the transformation buffers sort
of merged...
This could mean the transformation buffers themselfes don't actually have to
contain any memory at all...
Except for pointers to indicate where they start and their length or where
they end.
This is pretty efficient... however this does require retrieving extra
pointers... but this should be able to happen in parallel sort of ?
Or maybe this makes the algorithm bad... because now the processor has to
wait again on the pointers... hmm.
Maybe the swap idea wasn't so bad after all... at least it doesn't require
so much complexity and pointers and stuff.
Bye,
Skybuck. ;) :)
Skybuck Flying
I woke up and realized I missed something.
Each transformation is not a byte, but an integer (32 bit).
So this means the bandwidth requirement is actually 4 times it.
> So that's again 19 rounds... plus one extra for final copy.
>
> Is 20 rounds per channel... so that's a total of 60 rounds for rgb.
>
> That means
> 60 x 307200 bytes need to be copied per frame is: 18.432.000
>
> This needs to happen at least 30 frames per second so that's:
>
> 18432000 x 30 = 552.960.000 bytes per second.
x4 =
2.211.840.000
2 GB / sec.
So it's quickly approaching the bandwidth limitations of the system me
thinks.
And it still needs to do other stuff as well.
So it's starting to seem like wheeler is serious limitation.
Some things could be done:
1. Limit wheeler to smaller blocks for more speed.
2. Get rid of wheeler all together.
3. Keep big wheeler and other slow compression algorithms just to make the
codec a way to store video... even if it's slow ;)
Like a storage system :)
Maybe even make different versions... one for playing video for fun.
And one for storage system ;)
Bye,
Skybuck.
Skybuck Flying
I think I came up with a nice/simple solution how to make the wheeler decode
faster...
I still have to try it... but I think it's gonna work.
It doesn't require a little bit more storage space but it should double the
decode performs.. or maybe even multiply if even more storage is used ;) :)
But for now just like my bubble-to-front invention I shall keep it a secret
! :P ;) :)
Bye,
Skybuck :)
hutch--
Did you think we had forgotten about you ? Now come on, you must have
returned to your manual self delusional ways again. Now you know what
to do, let go of your DICK, pick up the MOUSE, click on SHUTDOWN and
when the computer has turned off you can manually delude yourself in
perfectly good company (yourself) until you hit the roof.
If you need further instructions we can advise you on how to ejaculate
into outerspace but you will need a hotwired DILDO for that. :)
hanukas
Good.
Skybuck Flying
I never tried that idea... because it would probably not scale well.
However today I have a new idea... which might be possible.
BWT might actually be "vunerable" for a wait free or lock free algorithm or
whatever.
"Compare and Swap" might perform some magic on it ;)
And the real magic will be with the loading of the cpu cores L1 caches with
the data.
However I fear that this idea is ahead of it's time...
Each key is an integer.
For an image of 640x480 there would be: 307200 green keys, 307200 red keys,
307200 blue keys.
Each key being 4 bytes this would mean:
1228800 bytes for green keys,
1228800 bytes for blue keys,
1228800 bytes for red keys.
Roughly 1.18 MB per color.
My AMD X2 3800+ processor has 64 KB L1 cache per core... so assuming feature
processors will have caches like that then this would require:
1228800 / (64*1024) = 19 cores per color.
So that would mean: 3x19 = roughly 60 cores ?!
For now that's way too much... maybe the data can be "compressed a bit" to
better fit into the data caches ;)
For an image of 640x480 the maximum index is close to 307200.
So bits needed for that is: log10( 307200 ) / log10( 2 ) = log2( 307200 ) =
18.22 bits so that's 19 bits.
Assuming that all bits can nicely be shifted together... than this gives new
calculation:
19 * 307200 = 5836800 bits / 8 = 729600 bytes per color.
So 729600 / 65536 = 12 cores.
So that's 3x12 = 36 cores.
Almost half...
Maybe graphics cards have something like compare and swap... but I don't
know about that ;)
An alternative idea could be to reduce the bwt to just one color... but this
might not give good compression result ?!? but could still be tried.
Then cores would go down to only 12 cores... which is still much more than
today has to offer ;)
This is all theory though... this assumes the algorithm will work and that
cas won't be too much of a bottleneck... and that the loading into the cores
can be done fastly, and just once preferbly, for maximum caching/speed
effects ofcourse ;)
However maybe some modest/slight speed up might be noticeable for dual core
processors which could prove that it works ;)
So maybe I try out this new idea... and that means that further details
about this new algorithm remain secret and in my head for now HAHA LOL =D
However I might ask some questions in the future how to load the L1 cache
real fast with data... because I am not completely sure about that how to do
that well ;)
Bye,
Skybuck.
Skybuck Flying
The idea is pretty much pretty simple:
"Using all the cpu cores L1 caches as one big L1 cache (by letting cpu's
communicate with each other "via cas" ;)) "...
And then add some other idea's to the mix ;) See () ;)
Question for you:
"Can it be done ? Can all cpu cores L1 caches be used as one big L1 cache by
some tricks maybe... or maybe some new architectural features ? ;)"
(I already revealed one of these possible tricks...: CAS :))
However I already told you toooooo much... no pseudo code for algorithm will
follow my lips are sealed ! :P ;) :)
Besides pseudo code only in the head yet :)
But it's good for me to document these hints and secret thoughts in case I
might ever forget them :):):) the rest I can figure that out myself based on
this ;)
Bye,
Skybuck.
Skybuck Flying
I just had an idea how to make the loading automatic.
For example for a dual core system:
core1:
if index to be retrieved is in lower half of total indexes then core1 will
retrieve it.
core2:
if index to be retrieved is in upper half of total indexes then core2 will
retrieve it.
This should make sure that core1 is filled with lower half indexes and that
core2 is filled with higher half indexes...
And this at least should give some caching effects for indexes that are near
to each other and were then already loaded...
However it would still be best to load the caches completely first at least
I would expect that to be better...
but ofcourse for now... the caches are not many and not large enough to
contain all data so for now this "dynamic loading of the cache" will have to
do... and all hope is placed on accidental cache hits ;)
However in a bad case it might not have cache hits at all... who knows ;)
Well there ya go so pseudo code for you guys after all ?!
Shitty man ! ;)
Final bit is something with:
"cas" into something :)
Question is: Will "cas" fuck up the cache ? :)
Bye,
Skybuck ;) :)
Skybuck Flying
I just programmed and tested a basic version of this idea to the best of my
abilities... and so far it seems to run much much much worse... then
anything else.
(By the way the cas was omitted it wasn't even needed ;))
Anyway... the problem seems to be that this probably causes massive thread
context switches... and insanely ammounts of wasted thread time...
Especially when the threads are much more than the number of cores...
The thread will just run and run and run and run... and all this time it has
nothing to do because the key is outside it's range...
And since the other threads aren't running it will have to wait until it's
time slice is over... so that another thread can finally run which updates
the key...
So this is a little problem...
However this problem might be solved by putting the thread to sleep if it
has nothing to do so that another thread can run...
A sleep(0) seems best here since this should force another thread to
immediatly run...
Maybe there is even a better solution.. or maybe this algorithm is just
f*cked ? ;)
Or maybe I didn't test it right.
So far tested: 100 keys, and one million keys... and 2 threads and 10
threads.
Maybe I should test with settings more close to the accumalted cache size...
However I am stinky... and I am low on food... so this will have to wait
because I have to go take a shower and buy food :)
This was interesting and funny to see/think about though... about this
thread wasting time problem which maybe only occurs if threads more than the
number of cores ? Or maybe it also occurs of threads the same ammount as
number of cores...
That kinda seems likely... because I can't imagine all threads running at
the same time... because the operating system has to run as well ofcourse...
and then user interface etc... so maybe the threads aren't actually running
at the same time... and that means that one thread will be waiting... for
the other thread to do it's work/update... so that ofcourse can't work...
but then maybe a sleep might solve it... but as I wrote that will have to be
tried and tested later on because right now my sack needs a wash ! LOL =D
(Just pretend I didn't write that LOL)
Bye,
Skybuck =D
Skybuck Flying
Instead of limiting the cores/threads to a certain index/pointer range...
they could be freeed to work on whatever they wanna/need to work.
However distributing the data across the cores might still be achieved by
manually somehow injecting data into the l1 caches so that it might perform
faster for certain cores... so that the cores can start racing against each
other...
This however would then require the use of cas to make updating of the keys
atomic and protect against race conditions and might cause other little
unknown problems to be solved first so not too sure about that...
But at least this would solve the "thread has nothing to do problem"... and
might also prevent "expensive" context switches which seem to use something
like 140 cycles or so... (from reading some website in the past) and thus
cycle times might go up in the future... so maybe preventing context
switches might be wise... so using the thread to do as much work as possible
could be wise...
So instead the data has to be distributed to the cores/l1 caches
"implicitly" so that some cores might run faster for certain lookups and
then might return faster and "win" the race ;) which would ultimately give a
little speed up thanks to more cache usage.
However then the question becomes how to distribute data implicitly to the
l1 data caches...
This could be done upfront... but then that would only work for anything
caches...
Another idea could be to do some random prefetches... or maybe some kind of
prediction logic which simply tries to load some data into the cores... like
a best effort gamble...
If cores get luckly then the data already there... this might work... and
would introduce probably only a little bit of overhead ?
Or maybe the prefetches might interfere with the normal lookups ? Hmmm...
But assuming the "respond" time is the bottleneck and not necessaryly the
ammount of lookups then this might work.
The assumption after all is: "the cpu is waiting for the answer from main
memory".
However issueing "multiple questions" to the "main memory" should probably
not worsen it... but more likely improve the responds time... since more
chance for "good answers in the cache" ! ;)
So the pseudo code could be usefull after all...
Instead of limiting the thread to a certain range... the pseudo code is used
for the prefetch logic...
In this case it could work as follows:
Half of the cache is imaginary "reserved" for "normal work".
Half of the cache is imaginary "reserved" for "distributed data".
This way some kind of distribution of the data across cores is achieved...
and at the same time... the core should also be able to work on data as it
normally would.
So 50% chance of cache hits for the "normal case".
So 50% chance of cache hits for the "distributed case" which could improve
the responds time if all cores/threads are running at the same time...
^ More data in cache that way...
So 50% is probably wasted on same data.
So 50% is used on unique data.
This could mean the range has to be reduced by two...
But then again maybe this idea is not necessary at all...
Maybe 99% of the cache could be used unique/distributed data... and then use
1% to do the actual normal work.
The idea is after all to let all threads/cores run at the same time in the
future.
Therefore the thread is penalized if it has to do all the work itself...
because the prefetch will constantly push out the data for the normal
case... and keep requesting the distributed data... to me this doesn't seem
to smart... but then again... nobody really knows the pattern of which the
data is distributed... so it could be good or bad... nobody really knows...
However I do know that my design in theory should work maybe a little bit
better...
So maybe going with 99% of cache for my distributed idea might be better
after all ;)
Anyway it could be highly interesting to prefetch in this fashion... so I
will try out this idea as well :)
Bye,
Skybuck.
Skybuck Flying
Yesterday I had an idea for parallel huffman...
Today I have an idea for parallel wheeler...
I think I now understand how to do parallel wheeler... it requires using a
little bit of extra space per cell...
That's all I am gonna say about it for now.
I am going to work out this new theory first to see if it could work and
then maybe I make a cpu implementation see if that actually works as well...
and then maybe a gpu implementation but if I remember correctly I would have
to alter some things for even more compression or so...
Oh yeah know I remember what the problem was.... the problem was probably
with the encoder and the sorting... if I can speed up sorting on gpu as well
then maybe altering way of encoding might not be necessary that would be
nice... then I can quickly release a lossless video codec for people to try
out...
I think such a video codec could be interesting for people doing lot's of
video processing... I am not sure how many people there are in the world
that do that regularly... I was also considering adding a little "spyware"
for the free version so I could collect some data on the number of copies
being used by people... but I am not sure if that would scare people away
and I would also need a website for it... probably... maybe not really...
but ok... and that kinda sux... website suck... they get overloaded... I
could also use some p2p technology of mine... but then the end user could
end up with a 4 gigabyte file just for ip's and such... plus 2 to 4 kb/sec
for p2p network. Maybe even more if security is needed.And there would be
major delays in the data... but a time stamp could solve that... but these
would get overriden quickly... so maybe p2p technology not a good choice for
it ;)
It would probably be crappy at best but at the same time kinda fun and could
be enough of an indication...
Another idea could be more simple: on installation an e-mail is sent to
me... but then my e-mail box would overflow quickly if many users...
probably not good idea either ! ;) :) But then again this would just be once
per installation. But this would require a e-mail service to be setup which
might not always be the case... and people might not wanna give out their
e-mail address for good privacy reasons.
Download counter comes to mind, php site comes to mind... http
activation/counter comes to mind. Well I shall give the webstuff a rest for
now and focus on this new algorithm idea.
Goodbye for now
Skybuck ! ;) :)
Skybuck Flying
well... need to try that out too... :)
Bye,
Skybuck.
Skybuck Flying
> Oh that reminds me I also had a little subtractor compression idea as
> well... need to try that out too... :)
I checked this simple idea out... it's samiliar to the paeth predictor...
I would call it a "previous color transform" ;)
I don't expect much from it...
I could try out different things though... like for example and "average" or
so... to see how that works out ;)
Just curious how a subtraction only would work out...
I could also try out a variation which does left pixel, top pixel or
diagonal pixel... to see if any works better for a certain frame... however
this would then require re-doing the compression for each one... it might be
nice for an experiment but probably not for a real codec ;)
Ok back to the parallel wheeler examination for me ! ;)
Bye,
Skybuck =D
Skybuck Flying
For now I designed a sequantial version which uses markings to indicate what
happens to certain sections of the wheeler.
The algorithm is based on my old idea of processing sections in parallel and
extending/moving them.
For parallel execution this algorithm has a number of problems:
1. The markings for a section might be updated twice or multiple times for
different sections. This would create "marking conflicts".
2. The extending/copieing would only be partial for certain sections and a
extra pass would have to be done to correct that.
3. Depending on the parallel implementation some unnecessary work is done.
To solve problem 1 could be issue, instead of manipulating the markings of a
section, the necessary changes for a section are kept in the section that
wants to make the change.
This would create a table containing all marking changes.
An extra algorithm would be necessary to scan for conflicts and solve the
conflicts somehow... this could be a sequential algorithm as a first
solution and maybe later a parallel solution could be found.
Solving problem 2 could also be handled by solution 1 or to make it more
easy a seperate algorithm could be done as well. Again this could first be
sequantial algorithm and maybe later a parallel algorithm.
Solving problem 3 is probably not really possible, though if the parallel
algorithm is executed in "degree of parallelism blocks" then some sections
could be prematurely marked and thus be skipped for further processing.
So far I am happy/content with the full sequantial algorithm for cpu.
For 16 keys the example required 5 passes if I stick to the original
algorithm.
A small modification could be made which would do more copies per pass which
could bring down the passes somewhat.
The question is if this would be a good or a bad thing... performance would
probably depending on memory organization and locality of data...
I am not sure if the modification could be considered an optimization or
not.
So I am not sure if the modification would be good for data
locality/copieing.
This is something that could be experimented with to see which version of
the algorith performs best... it could also be dependent on video data.
So what does this algorithm ultimately do ?
First of all it orders all the keys so that they can be traversed in
sequantial order for decode,
Another nice property is that the keys do not need to be shifted and are
already in place.
I am not sure if that is an actual feature of the algorithm or that the
example just happened to be like that... Further experimentation with an
actual implementation should quickly reveal this.
If it turns out that it's not at index 0 than that doesn't really have to be
a problem.
It can simply start at the primary key and move upwards through the array
for as far as the array size allows and then wrap once... memory
streaming/performance will/should still be ok !
One last question remains if the cpu is actually capable of executing
multiple fetches.
The final decode loop could look something like this:
for vIndex := 0 to NumberOfPixels-1 do
begin
Output[vIndex].Red := Input[ OrderedRedKeys[vIndex] ].mRed;
Output[vIndex].Green := Input[ OrderedGreenKeys[vIndex] ].mGreen;
Output[vIndex].Blue := Input[ OrderedBlueKeys[vIndex] ].mBlue;
end;
A fix would be needed if the primary key doesn't start at index 0. For now I
will not think about a fix because I want to ask a question first:
The question is what will happen to the cpu when it executes:
OrderedRedKeys[vIndex]
Will it wait until it has the key ?
It probably will...
However the nice thing is that the next keys are also streamed in via a
cache line...
So for the next loop it shouldn't have to wait anymore... thus the "chain of
pointers is broken" or to say it in other words: "the pointer chasing
problem is gone".
This leave one remaining problem with the caches:
The input size of 1 MB for an image of 640x480x3 (red,green,blue) bytes plus
the 3 ordered key arrays of each 640x480x4 (index integer) bytes which is
roughly another 4 MB might be way to large to fit into the caches.
So the decoding speed would probably still depend on accidental cache line
streaming because of "happy/lucky/data locality near video input data". :)
This is the same problem as the previous version of the wheeler algorithm.
It will be interesting to see if "solving the pointer chasing problem"
actually increases speed... or if speed is still determined by data locality
and cache sizes.
However something interesting is now possible too... the decoding could
actually be done on the gpu.
The output location/index of each pixel is known.
The input location/index of each pixel is known.
The ordered keys indexes of each pixel is known.
Therefore the ordered keys arrays can be fed to the gpu as "textures" and be
used as lookups.
This could solve the "cache size" problem of the cpu by moving it towards
the gpu.
pixel shader code could look something simple like:
Pixel.Red = Tex1D( RedSampler, Y * Width + X );
Pixel.Green = Tex1D( GreenSampler, Y * Width + X );
Pixel.Blue = Tex1D( BlueSampler, Y * Width + X );
This should work just perfectly.
The nice thing is I don't have to be worried about something else stealing
my shader because the shader is so simple... the magic doesn't happen in the
shader :)
The magic happens in the cpu code ! LOL :)
Most interesting.
The question remains what is the true speed/performance in practice and the
answer is the proof of the pudding ! ;) :)
So I will have to implement it and test it all out.
The decoding is so simple it can be done on cpu and/or on gpu... which
should make it real easy to compare results and also implement a switch for
the user or codec.
The codec could first do a performance test and then switch to either cpu or
gpu coding depending on which one is faster ! (Or use cpu code if gpu dll's
are malfunctioning/not present or if gpu simply not present or has no
support for opengl/shaders etc !) That's pretty cool too and probably
necessary for a real world video codec ! =D
^ most work on as many systems as possible ! =D (slow working video codec is
still better than no working video codec on slow systems ! ;) :) and working
video codec is still better than no working codec on very high speed cpu's
in the future which might not have gpu :))
Another possibility which I had in mind if using multi threading for the
wheeler... I don't think I actually tried that... using multi threading
might give better performance on cpu's which don't share caches... so I
think there is still some more performance to be gained for the cpu
version.... however ultimately the three red, green blue color bitmaps would
have to be merged together which could mean additional overhead... not sure
if it would be worth it.
For now I would already be very happy with good or super performance from
the gpu than at least people with gpu's could enjoy my new lossless video
codec ! ;) :) =D
Then later I could investigate even better algorithms than wheeler ;) :)
Now that I can solve wheeler I might be able to solve any pointing chase
problem (as long as it doesn't get to complex I guess !;) :)) ! who knows !
;) :)
Bye,
Skybuck.
Skybuck Flying
> actually be done on the gpu.
>
> The output location/index of each pixel is known.
> The input location/index of each pixel is known.
> The ordered keys indexes of each pixel is known.
>
> Therefore the ordered keys arrays can be fed to the gpu as "textures" and
> be used as lookups.
>
> This could solve the "cache size" problem of the cpu by moving it towards
> the gpu.
>
> pixel shader code could look something simple like:
>
> Pixel.Red = Tex1D( RedSampler, Y * Width + X );
> Pixel.Green = Tex1D( GreenSampler, Y * Width + X );
> Pixel.Blue = Tex1D( BlueSampler, Y * Width + X );
Actually I just realized something while playing quake 3 as relaxation lol
:)
I think gpu textures limited to 4096x4096, I think this applies to Tex1D as
well not just frame buffers
and such.
So the shader code above is not possible because it would require a texture
of 640x480 in 1D = close to one millionx1, so trying to write such shader
code would be a waste of time and ofcourse I don't want to be wasting any
time when coding.. especially writing useless code is shitty and
wastefull...
So I have to think it through a lllllitttle bit more to get it working...
it's probably not that hard and pretty trivial... not completely sure
actually because I haven't done any gpu texture mapping yet... I was
actually getting very close to that... so I have to do some more learning
and experimentation at that front...
But I think it's pretty obvious/simple solution:
Somehow translate the ordered keys array into a 2D array...
It might actually not be needed to do that because the "gl texture bind"
command/api actually just expects one single pointer to data...
So as long as the ordered keys array is a big sequantial block of memory
which it should be... then it should be easily mapped to 2D... no extra
copieing to 2d format necessary.
So all that's necessary is change the shader code a little bit... let's see
it should look something like:
Pixel.Red = Tex2D( RedSampler, X, Y );
Pixel.Green = Tex2D( GreenSampler, X, Y );
Pixel.Blue = Tex2D( BlueSampler, X, Y );
X,Y being the texture coordinate of the vertex quad etc... could even be
individual vertex positions but that's not necessary and would be crazy
overheadish ;) Just a nice quad will do.
Not sure if texture coordinates would be -1 to 1 or 0 to width and 0 to
height... I would prefer the last one... otherwise a little multiplication
and offsetting is needed...
Well that shouldn't be too hard to figure out... at least the tex2d will
probably do Y * Width + X so that should work.
So for me I guess it's now back to the boring gpu coding :)
Boooring :) LOL (Not really little bit fun/interesting too).
Or maybe I go write the new wheeler algorotum cpu code first... since that
can just be executed/plugged in without any further coding overhead.
Yeah I think that last one is pretty smart... because it could give an early
indication what the performance might be... though it could also be
deceptive and misleading... another disadventage of immediatly coding it
after I just invented it is that I don't give my brain time to cool down,
sleep a night on it... usually I will even find better algorithms the next
data or little improvements... though I already think this algorithm is
pretty good as it stands... On the other hand not coding it now could mean I
might loose interesting and not code it at all or I might not remember how
it worked though I think I documented it quite nicely... with example but
still... this is all kinda tricky... Then there is the slight "getting
tired" factor and getting a bit fuzzy factor but I still feel alright though
slight headache coming LOL.
Also maybe I am not ready yet to program the new algorithm because I still
have to think about the necessary data structures... I could try to figure
that out as I go and program it... or I might give it a rest and think about
it some more to see what is the most sensible solution...
Though I think it's pretty easy... array of some records to keep track of
information where the sections start and stop or so... what markings they
have... and maybe an output array to copy stuff too.
This could mean input section data and output section data... also maybe two
arrays... an input array and output array... and swap those for the next
pass.
Adjust markers etc...
Actually I didn't even make an algorithm yet... there is no real pseudo
code... there are some rules how to update the tables... there are only two
worked out examples... last one is the best one...
So I still need to pour it some more into a decent pseudo code algorith me
guesses/thinks :)
But I am pretty good at writing algorithm as a go along so I might not
really need that but it's still good to have it as a red wire taking me by
the hand through the algorithm/code implementation phase so I don't do any
thing stupid like forgetting crucial steps or so... like table updates or
markings :)
Though I don't really need the algorithm in a seperate document... I could
do a little skeleton for the code and then fill it all in...
Writing algorithms in pseudo code sometimes sux a bit... it will have all
kinds of little bugs and short comings which would be detect/found during
the implementation phase which would mean I would then have to go back to
the algorithm doc and update it there as well... which is pretty much
duplication of effort which kinda sucks :)
And I don't really plan on selling this algorithm because there would
probably be little interest in it for now though that might change in the
future :)
So maybe it would be good to have a nice algorithm description in case
somebody else ever wants to implement it :)
Then I could "sell it" and then I don't have to make the algorithm in the
future...
But then again... I could also just rip the algorithm out of the code and
shove that down their throast or even sell the source code... though I don't
like selling source code that much...that makes it less fun to watch if they
can implement it themselfes LOL.
There could be extra money in it for me: If you not able to implement the
algorithm yourself then you can "hire" some of my time "consultency" how you
can solve some issue's or so LOL :)
Though that might be perceived as being too greedy but hey... my time ain't
free you know ! ;) :) You gotta pay for it too ! =D LOL.
Ok peeps that's enough information/blogging leakage from me for now.
Takes care, peace out and thanks for reading if you did read it I bet you
found that interesting/fascinating didn't you ?! If not then piss off ! LOL.
:P ;) :)
Bye,
Skybuck =D
Skybuck Flying
There will be some overhead for implementating this algorithm... the
overhead could become larger and larger as the algorithm becomes more
advanced. (by for example implementing alternative version which does less
copies and less passes.)
And then the question rises if the overhead is not going to kill the
performance.
If it does kill the performance then ofcourse I am back at square one ! ;)
:) and doing it pointer-chased might be faster then...
So thinking the algorithm through some more how to turn it into parallel
algorithm might be more beneficial after all...
Though I could still implement a sequantial version for on the cpu... but
something inside me says it's not gonna be fast for 640x480 red colors ! and
that three times.
It's bandwith versus access time.
And my algorithm would also have some access time overhead which could
already kill it... just the overhead in pass 1 could already kill the
performance.
pass 1 is supposed to execute in parallel sorta of... not in sequence :)
So I think unfortunately enough I cheered a little bit too early and I shall
have to postpone it and think about a way to make it work better in parallel
!
Then it might have a chance of being faster ! ;) :)
Bye,
Skybuck.
Skybuck Flying
I gave it some more thought... and I think the problems for the parallel
version are solvable... I kinda knew it already you know ;) :)
In the first example I actually used multiple rows for the markings.
Each marking type had it's own row in the original example/first work out...
later to save space I compacted it into one row. Would have been nice for
the algorithm/memory too...
However using just one row for marking would create concurrency problems and
since the gpu has no "locking" mechnanics synchronization access to cells is
not possible.
And locking cells would/could be bad for performance as well...
So instead of using just one row it's back to the original example which
uses multiple rows for markings !
This way there is a sort of history available or a sort of "multiple views"
or "perceptions".
By examining all the marking rows it becomes easily possible to find/detect
conflicts.
So an intermediate pass between pass 1 and 2... let's call this the "solving
conflicts pass" will examine the markings...
And now comes a neat trick to turn "sequantialness" into "parallelness" :)
Normally the sequantialness is done by a loop, the loop changes some state
which affects the next iterations.
This sequantialness would decide who gets changed and who does not get
changed because the other one was already changed.
This behaviour can easily be translated/mimiced to parallel by using the
following simple trick:
By comparing indexes (which are supplied in parallel) it becomes possible to
mimic this logical "timewise/sequantial" behaviour with the following code
example:
if IndexOfCompetitor < IndexOfMyself then
begin
IndexOfComptetitor wins.
end;
So for example:
if 10 < 20 then
begin
10 wins.
end;
This gives a nice "switching capability" or "ranking capability" or
"ordering capability" or "first assignment capability" or "only execute if
we have lower rank than competitor".
Get it ? ;)
This will/should make sure that only one of them executes.
One could wonder if it is possible to integrate into one pass but that would
logically not be possible because the answer of the competitor might not be
available yet...
So to clearify the example above here is a somewhat expanded example:
Pass1:
Determine all answers of all cells/competitors/everybody.
Pass1.5 Solving conflicts:
Examine all answers of all cells/competitors/everybody.
The code now becomes more realistic like so:
if AnswerOfCompetitor[CompetitorIndex] conflicts with
AnswerOfMyself[MyselfIndex] then
begin
if CompetitorIndex < MySelfIndex then
begin
CompetitorIndex dominates and answer will be used. (Competitor out
ranks me (lower rank is winner))
end else
begin
MySelfIndex dominates and answer will be used. (I outrank
competitors (lower rank is winner))
end;
end;
This mimics first assignment principle and prevents overwrites.
Each cell can now adjust it's answer to depending on who won and each cell
can therefore prepare itself for the next pass.
Pass 2. Repeat algorithm of pass 1 etc.
Pass 2.5 conflict solving etc.
Pretty cool.
Bye,
Skybuck.
Skybuck Flying
description I was looking for ! ;) :)
"solving phase/pass":
if CompetitorIndex < MyIndex then
begin
// apply competitor solution first
// apply my solution next
end else
begin
// apply my solution first
// apply competitor solution next
end;
Bye,
Skybuck.
Skybuck Flying
Paeth predictor might also be parallizeable... pretty sure about that...
This was also a little performance eater ! ;)
I am starting to think the whole video codec is parallizeable :)
Except ofcourse the loading and streaming from/to disk. That needs to be
serial because first of all that's the way it works and second of all
becomes of compaction...
But the compaction could be done on gpu as well...
That leaves the harddisk as the only technology not parallizeable ?!?
But maybe that might change in the future with flash drive/ssd technology or
maybe even something new...
Hmm ;) :)
Bye,
Skybuck.
hutch--
Are you back to your old bad habits again, manually deluding yourself
on Usenet ? Isn't it time you swapped hands so you don't end up with
an extreme case of RSI ?
Now you know what to do, remove you DICK from your hand, pick up the
mouse, shut down your computer then you can manually delude yourself
until you hit the roof and we won't have to listen to you in the
process.