Re: Locality of allocations

From: Eric Taylor (et1_at_rocketship1.com)
Date: 09/20/05 

Date: Mon, 19 Sep 2005 23:06:24 -0700

Kasper Dupont wrote:

>
>
> So I have an idea about splitting it up. The most
> practical way to split this structure will give me a
> 28 byte structure with a pointer to a 528 byte char
> array.
>

In your other posts, you seem to have dealt with
the issues of locality of the smaller pieces, yet
are still unsatisfied with the performance.

I was struck with curiosity about this 528 byte
char array, which you did not describe any further.

A young grad student once remarked to me, "Virtual
memory is great, as long as you don't use it".

So, I was wondering if your efforts might be better spent
looking at a way to reduce/compress your memory - a tradeoff
of more cpu cycles to avoid paging. For example, do you need the
528 to be fixed in size. If you only access these sections
infrequently, and it's a batch run I think you said, could you
do some simple data compression on these (are they mostly
zeros etc.). Is this data text, or lots of differnt small items.

Do these change often, or are they mostly read/only?
Is this tree used for searching? Might you avoid touching many
nodes by using a hash table instead? Why did you choose a
tree? Of search/insert/remove/create/delete etc., which operations
are used most often.

Anyway, you've probably thought of all this, but sometimes one
forgets the old adage, if it hurts when I do this, well, then don't. :)

eric

Relevant Pages

  • Re: How long would it take a computer to completely "solve" chess?
    ... >> a rook against a king, search one ply farther to rule out stalemate ... >> and stop searching that branch. ... the tree will get to the same position (with same ... A position that has a known algorithm for winning. ...
    (sci.math)
  • Searching a treeview control
    ... My problem is in searching the tree. ... hChild = TreeView_GetChild(hWnd, hCurrent); ... returnPtr = FindTreeNode(winDlg, idCtl, hChild, nodeText); ...
    (microsoft.public.win32.programmer.ui)
  • Re: Smart Deleting
    ... You have a tree that you need to traverse to its root (highest ... subject in the various Access & SQL newsgroups. ... Try searching newsgroups: ...
    (microsoft.public.access.queries)
  • Re: Data structure for indexing on multiple keys.
    ... >> Please note that this is not about composite keys but supporting ... >>multiple keys for searching. ... > k-d Tree ... > P-Tree ...
    (comp.theory)
  • Re: Data structure for indexing on multiple keys.
    ... >> Please note that this is not about composite keys but supporting ... >>multiple keys for searching. ... > k-d Tree ... > P-Tree ...
    (comp.programming)