Prev: 2nd call - Applied Computing 2010: until 26 July 2010
Next: Opcode Parsing & Invalid Opcodes
From: jacko on 5 Jul 2010 12:27
Hi

Just wondered how useful this idea maybe.

64 bytes => 16 * 32 bit values

= 4 nodes.

Node
====

0. chain pointer
1. value
2. reference count
3. moved to please update pointer

The general idea is to migrate any referenced cell into the
referencing cache line or a closer one off the free list. This would
reduce information content if relative addressing was used. And frees
4 bits * 2 for pointer/typing. The algorithm would be more complex,
but prefetch would be more effective. Am I missing anything?

Cheers Jacko
From: MitchAlsup on 6 Jul 2010 22:32
Why don't you code up several examples, craft interesting datasets and
benchmarks using same, and come back to us with your conclusions?

Mitch
From: Morten Reistad on 7 Jul 2010 08:48
In article <04dd620b-badd-4e39-8c81-e8d0586f731e(a)w12g2000yqj.googlegroups.com>,
MitchAlsup <MitchAlsup(a)aol.com> wrote:
>Why don't you code up several examples, craft interesting datasets and
>benchmarks using same, and come back to us with your conclusions?
>
>Mitch

This approach seems an inside-out version of the "vertical trees"
that speed up b-trees, isam, etc.

You keep the nodes along a top and the red&black subtrees in the
same bucket, and at least one of the subsequent grandchildren
very close, instead of having horisontal locality you use vertical
locality.

Seems to give large speedups to some fundamental algorithms.

-- mrr

From: jacko on 7 Jul 2010 13:54
On 7 July, 03:32, MitchAlsup <MitchAl...(a)aol.com> wrote:
> Why don't you code up several examples, craft interesting datasets and
> benchmarks using same, and come back to us with your conclusions?
>
> Mitch

Not today, I'm frying multi precision integer arithmetic, and possible
virtal machine language specific opcodes.

Cheers Jacko
From: Brett Davis on 7 Jul 2010 22:15
In article <3l9eg7-j98.ln1(a)laptop.reistad.name>,
Morten Reistad <first(a)last.name> wrote:
> In article <04dd620b-badd-4e39-8c81-e8d0586f731e(a)w12g2000yqj.googlegroups.com>,
> MitchAlsup <MitchAlsup(a)aol.com> wrote:
> >Why don't you code up several examples, craft interesting datasets and
> >benchmarks using same, and come back to us with your conclusions?
>
> This approach seems an inside-out version of the "vertical trees"
> that speed up b-trees, isam, etc.
>
> You keep the nodes along a top and the red&black subtrees in the
> same bucket, and at least one of the subsequent grandchildren
> very close, instead of having horisontal locality you use vertical
> locality.
>
> Seems to give large speedups to some fundamental algorithms.

"You are Doing It Wrong"
http://queue.acm.org/detail.cfm?id=1814327

Ten times faster than B-Tree with B-Heap.

Brett
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: 2nd call - Applied Computing 2010: until 26 July 2010
Next: Opcode Parsing & Invalid Opcodes