I want to correct that last statement. With about 350M nodes currently in the tree (~30M of which fit into memory), I am averaging 0.06 disk reads per tree traversal. Must less than "several". In hindsight, "several" wasn't a good guess. The 0.06 number will get a little worse as the tree gets bigger, but probably not much.

Michael Williams wrote:
Those numbers are the average after the tree has grown to 1B nodes. I'm sure the cache hates me. Each tree traversal will likely make several reads from random locations in a 50 GB file.


Don Dailey wrote:
So you are saying that use disk memory for this? This could be pretty deceiving if most of your reads and writes are cached. What happens when your tree gets much bigger than available memory?

- Don



On Tue, May 12, 2009 at 1:18 PM, Michael Williams <michaelwilliam...@gmail.com <mailto:michaelwilliam...@gmail.com>> wrote:

    In my system, I can retrieve the children of any node at a rate of
    about 100k nodes/sec.

    And I can save nodes at a rate of over 1M nodes/sec (this is much
    faster because in my implementation, the operation is sequential on
    disk).

    Those numbers are from 6x6 testing.


    Don Dailey wrote:

        This is probably a good solution.   I don't believe the memory
        has to be very fast at all because even with light playouts you
are doing a LOT of computation between memory accesses. All of this must be tested of course. In fact I was
        considering if disk memory could not be utilized as a kind of
        cache.   The secret would be to store complete trees in disk
        memory, trees that are not likely to be utilized but can be
        utilized in a pinch.   The tree store and retrieved must
        outweigh by a large factor the amount of time spent creating the
        tree in the first place in order for this to pay off.
        My guess is that this is impractical, but it's fun to think
        about how it might be done.   I'm not sure how to do it without
        having a caching nightmare.


        - Don



        On Tue, May 12, 2009 at 12:41 PM, Michael Williams
        <michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>
        <mailto:michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>>> wrote:

           Don Dailey wrote:

               On Tue, May 12, 2009 at 12:16 PM, Michael Williams
               <michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>
               <mailto:michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>>
               <mailto:michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>

               <mailto:michaelwilliam...@gmail.com
        <mailto:michaelwilliam...@gmail.com>>>> wrote:

                  I have a trick  ;)

                  I am currently creating MCTS trees of over a billion
        nodes on
               my 4GB
                  machine.


               Ok,  I'll bite.    What is your solution?


           I use an SSD.  There are many details, of course.  But it's
        still in
           the works and I'm still making lots of changes and
        adjustments.  I
           seem to be able to "solve" (there are lots of definitions)
        6x6 Go in
           that when I use a komi of 3.5, it is unable to find a winning
        line
for white and when I use 4.5, it is unable to find a winning line
           for black.


           _______________________________________________
           computer-go mailing list
           computer-go@computer-go.org
        <mailto:computer-go@computer-go.org>
        <mailto:computer-go@computer-go.org
        <mailto:computer-go@computer-go.org>>

           http://www.computer-go.org/mailman/listinfo/computer-go/



------------------------------------------------------------------------


        _______________________________________________
        computer-go mailing list
        computer-go@computer-go.org <mailto:computer-go@computer-go.org>
        http://www.computer-go.org/mailman/listinfo/computer-go/


    _______________________________________________
    computer-go mailing list
    computer-go@computer-go.org <mailto:computer-go@computer-go.org>
    http://www.computer-go.org/mailman/listinfo/computer-go/



------------------------------------------------------------------------

_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/



_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Reply via email to