SummerOfCodeProposal cjhopman - Revision history

Esr: Hide historical instance of "SVN" from mediawiki search to avoid false positives.

2013-03-21T03:31:45Z

Hide historical instance of "SVN" from mediawiki search to avoid false positives.

Esr: Hide historical references to Subversion from the wiki search function

2013-03-21T00:21:04Z

Hide historical references to Subversion from the wiki search function

Cjhopman: /* WML Profiling */

2009-04-08T16:38:08Z

‎WML Profiling

Cjhopman: /* WML Profiling */

2009-04-08T16:37:10Z

‎WML Profiling

Cjhopman: /* String Representation */

2009-04-04T02:53:48Z

‎String Representation

Cjhopman: /* String Representation */

2009-04-04T02:40:57Z

‎String Representation

Cjhopman: /* Lazy Work */

2009-04-04T00:40:24Z

‎Lazy Work

Cjhopman: /* Lazy Work */

2009-04-04T00:39:44Z

‎Lazy Work

Cjhopman: /* Lazy Work */

2009-04-04T00:30:16Z

‎Lazy Work

Cjhopman: /* String Representation */

2009-04-03T21:46:42Z

‎String Representation

@@ Line 12: / Line 12: @@
 # What are you studying, subject, level and school?
 #* I am currently an undergraduate studying mathematics and computer science at the University of Wisconsin - Madison. I will be graduating in May and will be attending the computer science PhD program here in the fall.
-# If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for Wesnoth. If you have gained commit access to our SVN (during the evaluation period or earlier) please state so.
+# If you have contributed any patches to Wesnoth, please list them below. You can also list patches that have been submitted but not committed yet and patches that have not been specifically written for Wesnoth. If you have gained commit access to our S&shy;&shy;V&shy;&shy;N (during the evaluation period or earlier) please state so.
-#* I received commit access to the Wesnoth SVN early in 2008. There is a list of some of my [[#My contributions to Wesnoth|contributions]] below.
+#* I received commit access to the Wesnoth S&shy;&shy;V&shy;&shy;N early in 2008. There is a list of some of my [[#My contributions to Wesnoth|contributions]] below.
 ===Experience===

@@ Line 72: / Line 72: @@
 ===Practical considerations===
-# Are you familiar with any of the following tools or languages? Subversion, C++, Python, build environments
+# Are you familiar with any of the following tools or languages? Sub&shy;&shy;version, C++, Python, build environments
-#* I am very familiar with C++. I have used subversion enough that I can do the basics, I am not very familiar with creating and merging branches. I only have a little experience with both Python and build environments. With either of these, I currently can only do the most basic tasks.
+#* I am very familiar with C++. I have used sub&shy;&shy;version enough that I can do the basics, I am not very familiar with creating and merging branches. I only have a little experience with both Python and build environments. With either of these, I currently can only do the most basic tasks.
 # Which tools do you normally use for development? Why do you use them?
 #* Currently, I do almost all of my development in Linux, with a text editor, gdb and other command-line tools. Linux in general just makes development so much easier and the tools it provides are very powerful. In Windows (which I haven't really developed in in almost a year) I use Visual Studio 2005/2008. For debugging I feel it is even better than the tools available in Linux, and it has a few other nice features that may improve my productivity.

@@ Line 135: / Line 135: @@
 ===WML Profiling===
-EDIT: I have started doing some of this [[#cjhopman_wml|here]].<br><br>
+EDIT: I have started doing some of this [[cjhopman_wml|here]].<br><br>
 Before doing any optimizations, we need to know whether or not it has a possibility of making an improvement. Basically the assumptions that we have made are that there a lot of strings, a lot of these strings are not unique, and there are a lot of config objects. These are reasonable assumptions, but investigating them is one reason for me to do some extensive profiling.<br>
 The second reason to do profiling is to determine the benefit of optimizations that we do write. For this reason I have already set up a heap profiler so that I can see some higher level memory usage patterns (see [[Cjhopman profiling]]). I also plan to do some more intrusive programming, basically I want to be able to see the structure of the graph of config objects (with some info like size of current, size of all children, etc.). Also, I will want to see the distribution of strings in tag names, attribute keys and attribute values. This will be the first thing that I do for this project, currently scheduled to be done before the actual start of coding time.

@@ Line 135: / Line 135: @@
 ===WML Profiling===
 Before doing any optimizations, we need to know whether or not it has a possibility of making an improvement. Basically the assumptions that we have made are that there a lot of strings, a lot of these strings are not unique, and there are a lot of config objects. These are reasonable assumptions, but investigating them is one reason for me to do some extensive profiling.<br>
 The second reason to do profiling is to determine the benefit of optimizations that we do write. For this reason I have already set up a heap profiler so that I can see some higher level memory usage patterns (see [[Cjhopman profiling]]). I also plan to do some more intrusive programming, basically I want to be able to see the structure of the graph of config objects (with some info like size of current, size of all children, etc.). Also, I will want to see the distribution of strings in tag names, attribute keys and attribute values. This will be the first thing that I do for this project, currently scheduled to be done before the actual start of coding time.

@@ Line 97: / Line 97: @@
 ''More info available [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4N56BWF-5&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=067aef2a68139cd8694dcdab5d847db3 here] (I was unable to find a free version of this paper).''<br><br>
 '''Move-to-front chaining'''<br>
-In this variant the hash table is an array of linked lists. When we do lookups, the node that we find is moved to the front of its respective list. This move-to-front heuristic makes the hash table very efficient when there is a skew in the distribution of looked up words (as is likely the case with WML). The downside to this method is that it has more memory overhead per distinct string (due to the linked list pointer). As we will be allocating a lot of these listnodes, this is a nearly perfect opportunity to use Boost.Pool so that we don't actually do a bunch of small memory allocations.<br>
+In this variant the hash table is an array of linked lists. When we do lookups, the node that we find is moved to the front of its respective list. This move-to-front heuristic makes the hash table very efficient when there is a skew in the distribution of looked up words (as is likely the case with WML). The downside to this method is that it has more memory overhead per distinct string (due to the linked list pointer). We would likely hold a large block of listnodes in a vector or deque so that they don't all require a small memory allocation.<br>
 ''More info on efficiency of this implementation [http://goanna.cs.rmit.edu.au/~jz/fulltext/ipl01.pdf].''<br><br>
 '''Chaining with dynamic array'''<br>

@@ Line 94: / Line 94: @@
 My primary idea is to use a hash table to store the strings. The problem is that a basic linear-probing hash table performs very poorly at high load factors and so is not very memory-efficient if we want decent performance. There are a couple of other implementations that would be more memory-efficient. Each of these implementations are efficient at high load factors.<br><br>
 '''Blocked cuckoo hashing'''<br>
-One variant that would be good for this project is blocked cuckoo hashing, a variant of [http://en.wikipedia.org/wiki/Cuckoo_hashing cuckoo hashing] where each position in the table can hold some fixed amount of keys. There are several benefits to this implementation. At a very high ( > 99.9% ) load factor this implementation is still efficient and has very little memory overhead. The storage needed for blocked cuckoo hashing can be allocated as one large contiguous block. One downside is that the table has a fixed size and resizing the hash table would be difficult as it requires updating all the indices (the easiest way to do this adds an extra pointer per distinct string). A better option than resizing the table would be to have a backup stash. This could be a simple vector, but it would likely be better for it to be a smaller hash table that more gracefully handles dynamic size requirements.<br>
+One variant that would be good for this project is blocked cuckoo hashing, a variant of [http://en.wikipedia.org/wiki/Cuckoo_hashing cuckoo hashing] where each position in the table can hold some fixed amount of keys. There are several benefits to this implementation. At a very high ( > 99.9% ) load factor this implementation is still efficient and has very little memory overhead. The storage needed for blocked cuckoo hashing can be allocated as one large contiguous block. One downside is that insertions can move elements to different buckets and so our "indices" will need to be updateable. This likely means that they would need an extra level of indirection so they can point to something that doesn't move. Also, with blocked cuckoo hashing the table has a fixed constant size, if it gets too large we would have to resize it which can be quite slow. A better option than resizing the table would be to have a backup stash. This could be a simple vector, but it would likely be better for it to be a smaller hash table that more gracefully handles dynamic size requirements.<br>
 ''More info available [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4N56BWF-5&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=067aef2a68139cd8694dcdab5d847db3 here] (I was unable to find a free version of this paper).''<br><br>
 '''Move-to-front chaining'''<br>
@@ Line 102: / Line 102: @@
 Here we replace the linked list with a dynamically sized array. This has a bit less memory overhead but the allocated memory will not be in a single contiguous allocation. Also, in this method is it more difficult to use the move-to-front optimization as it would require updating the indices. Without that optimization, this is likely the least cpu-efficient of the three implementations.<br><br>
 I believe that the best for this project will be one of the first two (though once one is working it will be quite simple to drop in another as the interfaces are the same).<br><br>
-For this project, if profiling shows that there is a lot of non-distinct strings as is expected, I will implement at least one of the first two variants. The first has an overhead of at least 32 bits per distinct string(assuming 32 bit size_t) and the second at least 64. Again, profiling will show if it will be worth it.<br><br>
+For this project, if profiling shows that there is a lot of non-distinct strings as is expected, I will implement at least one of the first two variants.<br><br>
 Note: Another option for this would be a B-tree with large branching. This will likely have more overhead than the hashing options. I do not currently plan to implement this during gsoc, though again it would have the same (or very similar) interface as the hash tables and should be easy to drop in and profile.<br><br>

@@ Line 131: / Line 131: @@
 This optimization actually has the potential to greatly reduce memory usage. Implementing this will likely hit several parts of the code (config, config_cache, parser, ...).<br><br>
-'''EDIT'''<br>
+'''EDIT''' 9/4/09 00:40 GMT <br>
 Lazy optimizations is not really a good title for these as I actually intend for config objects to move back and forth between these states. That is, we should be able to, when constructing a config object, tell it which of the three states to be in. And we should be able to tell it at any time to go into any of the three states.<br><br>

@@ Line 128: / Line 128: @@
 While lazy loading will cut memory usage of a config object by, basically, 100%, I expect lazy construction to cut it by as much as 50%. The benefit of lazy construction would be that construction of the object once it is needed will not have to go to disk and so will be faster.<br><br>
-If we wanted to get really aggressive, we could have either of these lazy schemes actually store some more information so that construction would not require full parsing. In particular, I am thinking that we could have each tag stored with its length, then when we need to build a thing we can do it much more quickly. One benefit of this is that it would allow us to reasonably unload a lot of WML that we think won't be needed.<br>
+If we have these lazy schemes actually store some more information so that construction would not require full parsing. In particular, I am thinking that we could have each tag stored with its length, then when we need to build a thing we can do it much more quickly. This would allow us to aggressively unload WML that we think won't be needed.<br>
 This optimization actually has the potential to greatly reduce memory usage. Implementing this will likely hit several parts of the code (config, config_cache, parser, ...).<br><br>