Re^2: Designing a cache data structure (linked list)

I dunno. I got pretty badly burned by splice trying to compete using a heap, and that didn't require managing references, just index math. How do you intend to set this up?

Makeshifts last the longest.

Comment on Re^2: Designing a cache data structure (linked list)

Replies are listed 'Best First'.
Re^3: Designing a cache data structure (splice) by tye (Sage) on Feb 21, 2005 at 05:58 UTC
"O(1) Perl opcodes vs. splice" doesn't really compare to "O(log(N)) Perl opcodes vs. splice", especially when the constant multiplier for the O(1) is quite small. Splice might be efficient enough that the point where splice's O(N) nature finally takes over the small constant is a fairly large N. But I consider trying to optimize the simple O(1) linked list to be micro optimization and I don't plan to spend time futzing with benchmarks to see if an O(N) solution is a bit faster for the cache sizes I predict (perhaps quite inaccurately, in the long run). - tye Read more... (176 Bytes)	[reply]

Replies are listed 'Best First'.

Re^3: Designing a cache data structure (splice)
by tye (Sage) on Feb 21, 2005 at 05:58 UTC

"O(1) Perl opcodes vs. splice" doesn't really compare to "O(log(N)) Perl opcodes vs. splice", especially when the constant multiplier for the O(1) is quite small.

Splice might be efficient enough that the point where splice's O(N) nature finally takes over the small constant is a fairly large N.

But I consider trying to optimize the simple O(1) linked list to be micro optimization and I don't plan to spend time futzing with benchmarks to see if an O(N) solution is a bit faster for the cache sizes I predict (perhaps quite inaccurately, in the long run).

- tye