Why? Reducing waste. Making game state smaller.
Posted: 02 Jul 2011, 16:25"Why?"
first, i think i owe an explanation for my recent meddlings with the svn trunk, despite the fact that most of my work (on minimax) is supposed to be on a branch. summary: i have been working on the trunk to make the braids-minimax branch easier to merge.
in the near future, i may be asking to merge some of my smaller changes currently on the braids-minimax branch toward the trunk. i'll try to describe them in a post first. i can also post an svn diff before committing the changes, if people want to review them.
but before that there are a few things i'd like to change about how forge uses heap memory.
"Reducing waste."
for starters, i know i can make forge faster and more memory efficient by having CardFactory.getCards (and perhaps CardFactory.getAllCards) return an immutable Iterable instead of a list. if i am able to convert both, we will no longer need the allCards field in CardFactory; instead, those two methods will safely iterate over the values in CardFactory.map. (i can wrap the map's value iterator with an immutable iterator that does not support the remove method.) that list has several thousand elements, and i'm pretty sure i can just make it disappear.
this affects a lot of files, especially the ones that i foretold in r10084.
"Making game state smaller."
second, for minimax, we will need to make the game state more memory efficient. one way to do this is to use trees {TreeMap, TreeSet} instead of hashes {HashMap, Hashtable, HashSet} in fields that comprise the game state. hashes, while potentially very fast, usually have large amounts of null pointers inside them, depending on the load factor. this is overhead. each pointer is using up to 64 bits. why trees? they are more memory efficient. trees' get and put methods take a little longer than a hash
, but they only have null pointers at their leaves. java keeps its trees balanced, and a balanced tree has at most (2 * ceiling(ln(n))) (2 * ceiling(log2(n))) null pointers, i think. n is the number of items in the tree. if my math is wrong, please correct me.
from looking at the code, this also means i may need to change some methods' signatures to use Map<X,Y> instead of Hashtable or HashMap. replacing these specific class types with interface types decouples them from implementation, which is a good design practice.
Edit: if the hash's keys have evenly distributed hash codes. in the worst case, all of a hash's contents go into the same bucket, so their worst case time for a get or put is proportional to n, the number of keys. but a balanced tree's worst case time is always proportional to ceiling(log2(n)). so, trees have a second advantage in unusual situations.
first, i think i owe an explanation for my recent meddlings with the svn trunk, despite the fact that most of my work (on minimax) is supposed to be on a branch. summary: i have been working on the trunk to make the braids-minimax branch easier to merge.
- to keep the braids-minimax branch up to date, i have to merge the changes from the trunk to the branch. merging in svn has been nightmarish. i sometimes get strange error messages when i run svn merge. for instance, it's common for svn merge to fail in the res folder because of an error returned from a PROPFIND request. to work around this, merging becomes a multiple step process. first i merge with `--depth immediates' on the parent and then with `--depth infinity' on the subdirectories. if a subdirectory fails, i apply these two steps recursively to it and its subdirectories.
- resolving conflicts from merging is time consuming and somewhat unnerving. i am sometimes unsure of whether i am semantically breaking something. after my prior merge from r9969, i had reverted some of my cosmetic changes to reduce the number of conflicts. i thought the next merge would go much more smoothly. well, it didn't. it resulted in 30 conflicts in source code that i must resolve manually.
- merging is often a long process, and i find myself with extra time while i babysit it, so my natural tendency is to work on the trunk along with everyone else.
in the near future, i may be asking to merge some of my smaller changes currently on the braids-minimax branch toward the trunk. i'll try to describe them in a post first. i can also post an svn diff before committing the changes, if people want to review them.
but before that there are a few things i'd like to change about how forge uses heap memory.
"Reducing waste."
for starters, i know i can make forge faster and more memory efficient by having CardFactory.getCards (and perhaps CardFactory.getAllCards) return an immutable Iterable instead of a list. if i am able to convert both, we will no longer need the allCards field in CardFactory; instead, those two methods will safely iterate over the values in CardFactory.map. (i can wrap the map's value iterator with an immutable iterator that does not support the remove method.) that list has several thousand elements, and i'm pretty sure i can just make it disappear.
this affects a lot of files, especially the ones that i foretold in r10084.
"Making game state smaller."
second, for minimax, we will need to make the game state more memory efficient. one way to do this is to use trees {TreeMap, TreeSet} instead of hashes {HashMap, Hashtable, HashSet} in fields that comprise the game state. hashes, while potentially very fast, usually have large amounts of null pointers inside them, depending on the load factor. this is overhead. each pointer is using up to 64 bits. why trees? they are more memory efficient. trees' get and put methods take a little longer than a hash
, but they only have null pointers at their leaves. java keeps its trees balanced, and a balanced tree has at most from looking at the code, this also means i may need to change some methods' signatures to use Map<X,Y> instead of Hashtable or HashMap. replacing these specific class types with interface types decouples them from implementation, which is a good design practice.
Edit:
if the hash's keys have evenly distributed hash codes. in the worst case, all of a hash's contents go into the same bucket, so their worst case time for a get or put is proportional to n, the number of keys. but a balanced tree's worst case time is always proportional to ceiling(log2(n)). so, trees have a second advantage in unusual situations.
it's interesting you should mention this now, because i am ready to throw in the towel with the minimax branch. 
it has gone too far. by that i mean it has changed too many lines of code in existing files. i have been spending all of my time on that branch merging and no time improving minimax since its creation. :frustrated:
. . . i was just getting used to svn and all its quirks.