View mode: basic / threaded / horizontal-split · Log in · Help
June 11, 2012
Re: Making generalized Trie type in D
On Monday, 11 June 2012 at 18:23:39 UTC, Roman D. Boiko wrote:
> On Monday, 11 June 2012 at 18:16:45 UTC, Dmitry Olshansky wrote:
>> I meant an operation pseudo-XOR x P^ y where x is part of 
>> snapshot and y is part of diff page.
>>
>> x P^ y == x      when y == T.init
>> x P^ y == y      when y != T.init
> I understood, just mentioned some alternatives (maybe not 
> reasonable given your trie implementation).
Or probably not understood :)

Why pseudo?
June 11, 2012
Re: Making generalized Trie type in D
On Monday, 11 June 2012 at 18:27:58 UTC, Roman D. Boiko wrote:
> On Monday, 11 June 2012 at 18:23:39 UTC, Roman D. Boiko wrote:
>> On Monday, 11 June 2012 at 18:16:45 UTC, Dmitry Olshansky 
>> wrote:
>>> I meant an operation pseudo-XOR x P^ y where x is part of 
>>> snapshot and y is part of diff page.
>>>
>>> x P^ y == x      when y == T.init
>>> x P^ y == y      when y != T.init
>> I understood, just mentioned some alternatives (maybe not 
>> reasonable given your trie implementation).
> Or probably not understood :)
>
> Why pseudo?
Is this article somehow related, or just uses the same term?
http://iwct.sjtu.edu.cn/Personal/mxtao/paper/liujc_icc11_PID1075548.pdf

I couldn't google anything more useful so far.
June 11, 2012
Re: Making generalized Trie type in D
On 11.06.2012 22:30, Roman D. Boiko wrote:
> On Monday, 11 June 2012 at 18:27:58 UTC, Roman D. Boiko wrote:
>> On Monday, 11 June 2012 at 18:23:39 UTC, Roman D. Boiko wrote:
>>> On Monday, 11 June 2012 at 18:16:45 UTC, Dmitry Olshansky wrote:
>>>> I meant an operation pseudo-XOR x P^ y where x is part of snapshot
>>>> and y is part of diff page.
>>>>
>>>> x P^ y == x when y == T.init
>>>> x P^ y == y when y != T.init
>>> I understood, just mentioned some alternatives (maybe not reasonable
>>> given your trie implementation).
>> Or probably not understood :)
>>
>> Why pseudo?
0 ^ 0 = 1 while T.init P^ T.init == T.init :)
other are almot the same
but
1 ^ 1 = 0 while x P^ y == y
So it's not symmetric when x,y != T.init for starters ;)

> Is this article somehow related, or just uses the same term?
> http://iwct.sjtu.edu.cn/Personal/mxtao/paper/liujc_icc11_PID1075548.pdf
>
looks like it might be but I can't penetrate this scientish somehow ( I 
usually can) in any case I believe it's more of coincidence.

-- 
Dmitry Olshansky
June 24, 2012
Re: Making generalized Trie type in D
On Monday, 11 June 2012 at 18:42:14 UTC, Dmitry Olshansky wrote:
> 0 ^ 0 = 1 while T.init P^ T.init == T.init :)
> other are almot the same but
> 1 ^ 1 = 0 while x P^ y == y
> So it's not symmetric when x,y != T.init for starters ;)

Just a remark that DCT no longer needs tries to be immutable, 
since I decided not to backtrack which strings affect which 
syntax elements. OTOH, it is important to be able to do updates 
and reads at any time (intermixed).

Another note is that XOR makes sense only if you plan to do 
reverse transforms, or expect to pack diffs (if they will be 
sparse). Otherwise it would be more efficient to store new values 
directly.
June 24, 2012
Re: Making generalized Trie type in D
On 24-Jun-12 14:50, Roman D. Boiko wrote:
> On Monday, 11 June 2012 at 18:42:14 UTC, Dmitry Olshansky wrote:
>> 0 ^ 0 = 1 while T.init P^ T.init == T.init :)
>> other are almot the same but
>> 1 ^ 1 = 0 while x P^ y == y
>> So it's not symmetric when x,y != T.init for starters ;)
>
> Just a remark that DCT no longer needs tries to be immutable, since I
> decided not to backtrack which strings affect which syntax elements.
> OTOH, it is important to be able to do updates and reads at any time
> (intermixed).
>
> Another note is that XOR makes sense only if you plan to do reverse
> transforms, or expect to pack diffs (if they will be sparse). Otherwise
> it would be more efficient to store new values directly.

Storing new values directly is no easy trick as you need crawl page 
tables all the way up to see if this value corresponds to multiple 
indexes. Well something similar happens with diff trie anyway.

But diffs are indeed very sparse, and the trie itself usually also sparse.
-- 
Dmitry Olshansky
July 19, 2012
Re: Making generalized Trie type in D
Am Mon, 04 Jun 2012 23:18:31 +0400
schrieb Dmitry Olshansky <dmitry.olsh@gmail.com>:

> Compiler is like a nasty 
> stepchild it will give up on generating good old jump tables given any 
> reason it finds justifiable. (but it may use few small jump tables + 
> binary search, could be fine... if not in a tight loop!)

Looks, like you are back in control.

From http://gcc.gnu.org/gcc-4.7/changes.html :

** General Optimizer Improvements **

Support for a new parameter --param case-values-threshold=n was added to allow users to control the cutoff between doing switch statements as a series of if statements and using a jump table.

-- 
Marco
Next ›   Last »
1 2 3 4
Top | Discussion index | About this forum | D home