ssssshhhrink!

I've done some interesting experiments during the last days. The result of those experiments is the first (or: at least the first I know about) Huffman entropy encoding implementation (plus a word-replacement precoding for additional compression) written in Lua. Well, actually I've only implemented the decoder in Lua, the matching encoder is implemented in Java, because I had a practical use for all of this in mind: I intend to use this to save a few hundred kilobytes of the memory space that's taken by the quest objective texts in the MobMap quest database (and another few hundred kilobytes in a different, new database that's gonna be added in the next MobMap version :D ).

Aside from that practical use, it was kind of fun and a definitive learning experience to implement a data compression and decompression algorithm myself with the additional challenge to get the decompressor to work in the Lua environment.
This entry was posted by Slarti on Monday, June 25. 2007 at 05:23. You can leave a response, or trackback from your own blog.

Trackbacks

Trackback specific URI for this entry

    No Trackbacks

Comments

Display comments as (Linear | Threaded)

  1. Fin says:
    #1 2007-06-26 00:45 (Reply)

    Hello. Apologies for posting this here, but I wasn't sure where to send this - that being what I'm inquiring about: where should I send feature requests and bug reports?

    In case here is OK, I think there's a bug with the merchants bit (possibly not, but I don't understand how it should work otherwise). Basically if I type "Shattrath" into the "Zone" field under the Merchants tab, there are no vendors listed.

    Also, a feature request: would it be possible to add profession levels to the Recipes section?

    Cheers, and thanks for a wonderful cheaHHHHtool. :)

    - Fin

  2. Fred says:
    #2 2007-06-26 17:48 (Reply)

    Uhh hey, I found some error: My monitor resoluion was on 1024x768 first... now that I changed it to 1280x1024, the dots on the worldmap are not in the right positions... they are just moved away from their correct positions. Maybe you could fix that somehow?! =(

  3. Fin says:
    #3 2007-06-28 19:53 (Reply)

    Oh well, I guess you're not interested in bug reports and feature requests; fair enough. Thanks again for MobMap!

  4. CWDG-Cosin says:
    #4 2007-06-30 01:12 (Reply)

    I found that lots of the mobmap code is ugly and inefficient. I think if you do more optimization work on it, it would be better.

    For Example :
    MobMap_GetIDByName : Seach the large table to find a matched string and return it's index. If the table is more than 10000 items, it average need do 5000 times string compare.
    Suggest : Create reflection table for the special data table when mobmap loaded, then you can get the index directly.

    MobMap_ParseQuestObjective (any other function like this):
    -------------------------------
    -- Part A
    for w in string.gmatch(filtered, "%S+") do
    ...
    -------------------------------
    -- Part B
    for startingpoint=0,partcount-1,1 do
    for length=partcount-startingpoint,1,-1 do
    ...
    -------------------------------
    Suggest:
    Part A : Analyze string, save the word break position to the table
    Part B : Just use the table created by Part A to get the string.
    str = string.sub(filtered, 1, [i])

  5. CWDG-Cosin says:
    #4.1 2007-06-30 01:17 (Reply)

    Some code is filtered.

    MobMap_GetIDByName = MobMap_Get{xxx}IDByName

    str = string.sub(filtered, 1, [i]) = str = string.sub(filtered, 1, {Part A Create Table}[i])

  6. Slartie says:
    #4.1.1 2007-06-30 13:18 (Reply)

    Actually the code is relatively efficient - memory efficent, I mean, not CPU efficient. Memory efficiency had a much higher priority than CPU efficiency during development, because nobody cares if MobMap takes 100 msecs longer to display some data while they are not fighting (which is the usual way MobMap is used), but using up more memory than necessary all the time and thus making garbage collection more complex and frequent even during fights is definitely a condition to avoid.

    Those tablescans are actually pretty fast in practice - not nearly as fast as using an inverse table, of course, but fast enough to be a viable solution with zero additional memory overhead. If I would create an inverse table of 10k string entries like you suggested, I would use up an additional amount of 32 bytes (for the table itself) plus 10k*80 bytes (a string indexed value in a table is very expensive and costs 80 bytes) = 800kbyte more memory, which would almost double the memory space needed by the primary table. That just isn't worth the (not too noticeable) speed increase - at least in my eyes. I might however put in an option for the user like "optimize for faster response times (needs more memory though)" that enables the generation of inverse tables instead of tablescans to give that choice to the user.

    As for your second suggestion: judging from the code you posted in your second comment, you seem to have missed one important detail about that string search: it does not always start at position 1 (that is, the first word in the objective text), but increases that starting position to the second, third, ... word in the objective. I could still adapt it to do that, but I don't really see the big advantage over how it's currently done.

  7. CWDG-Cosin says:
    #4.1.1.1 2007-06-30 14:35 (Reply)

    In fact, on my laptop, search mob name takes nearly 1 sec or more than 1 sec, obviously a delay, if it just takes 100 ms, I also think it's not necessary to create the inverse table. On the other hand, a computer can play wow at lease has more than 512 mb memory, 800 kb is too small.

    About garbage collection, keep it's reference as cache after create the inverse table. if you keep the reference, system won't gc it.

    Important : series of mobmap_Get{xxx}IDByName are basic functions. It is called frequently.

    I will show you detail information about the second suggestion.
    string : str = "Actually the code is relatively efficient"
    word break pos table : tbPos = {{1,8},{10,3},{14,4},{19,2},{22,10},{33,9}}
    each item format : {Start Pos, Word Length (Not Include Space)}
    Then you can get any part of this string
    iWordCount = #tbPos -- table.getn(tbPos) in lua 5.0
    iStart -- Start word index in tbPos
    iEnd -- End word index in tbPos
    string.sub(str, tbPos[iStart][1], tbPos[iEnd][1] + tbPos[iEnd][2] -1)

  8. Slarti says:
    #4.1.1.1.1 2007-06-30 15:19 (Reply)

    The 100 msecs were the time needed on my desktop computer, but I see that this might be much more on other machines.

    Of course the garbage collector will never collect the inverse table, but it will have to iterate over it in every gc cycle to determine if it (or any referenced strings) can be gced. And gc is likely to happen more often as more memory is used. That's the overhead I'm trying to avoid by keeping the memory footprint down to a minimum, because a gc cycle can very well happen in mid-fight where any further delay is unwelcome.

    But I think the best solution would be to give the user a choice between smaller memory footprint or faster response times. That way everyone can decide based on his own computers' behavior.

    Thanks for the clarification on the second suggestion. I think I'm going to have to do a little function profiling to find out whether this solution is faster than the "tokenize string into words and combine the words in a loop later"-approach in place now.

  9. CWDG-Cosin says:
    #4.1.1.1.1.1 2007-06-30 16:11 (Reply)

    I don't care the efficiency of gc. There are thousands of wow API functions, const variables in the Global Table, and thousands of functions and variables used by other addons. If gc system can't resolve it, the whole wow ui system will lag. Your mobmap would not escape the fate however.

    Of course, let the users choose which is the better solution.

  10. Slartie says:
    #4.1.1.1.1.1.1 2007-06-30 18:00 (Reply)

    Oh, I do care. Cause if every addon developer just uses memory like "oh well most users have >1gig of RAM, so using xx megabytes for my addon won't matter anyway", we get to see UI configurations with >100 megabytes of RAM usage. Each single addon "doesn't matter", but the sum of all addons does have a noticeable impact on both UI memory usage and gc time/frequency.

    I have just finished integrating the optional use of inverse tables into the MobMap database functions whereever it was appropriate. I measured a decrease in the response delay by ~100 msecs to something below 20 msecs (the exact number depends on the mob name, of course), and an increase in permanent memory usage by ~1.8 megabytes (having all databases loaded and all inverse tables built) on my machine. However, if this optimization yields more time savings on other peoples computers, then it was worth implementing it. The option to switch it on will be included in the next version of MobMap (which will probably be released in the very near future).

    Thanks again for the suggestion.

  11. CWDG-Cosin says:
    #4.1.1.2 2007-06-30 14:50 (Reply)

    PS: A Monster name in english may be just 2 words. In Chinese it may be more than 5-6 chars.If the mob name table contain 15k items, English version db will only be searched 30k times, but the Chinese version db have to be searched 75k - 90k times.

  12. CWDG-Cosin says:
    #5 2007-07-01 02:05 (Reply)

    Another Suggestion:
    Code like this : {xxx} = MobMap_Mask(data, mobmap_poweroftwo[{yyy}], mobmap_poweroftwo[{zzz}]);

    I searched all mobmap code, MobMap_Mask and mobmap_poweroftwo are used only in this way. I think you can create a new function instead of MobMap_Mask.
    -----------------------------------------
    function MobMap_GetField(data, iBitShift, iBitCount)
    local number1 = bit.rshift(iBitShift)
    local number2 = bit.lshift(1, iBitCount)
    if(MOBMAP_ISONAMAC) then
    if(number1 < 0) then
    return 0;
    else
    return floor(number1 % number2);
    end
    else
    return bit.band(number1, number2 - 1);
    end
    end
    -----------------------------------------
    {xxx} = MobMap_GetField(data, {yyy}, {zzz});

    It is hard to say which is more faster. If uses the new function, mobmap_poweroftwo not in need.

    BTW : On Mac, bit functions are different from x86? I think script language should be same at any platform. If I implement the bit lib of lua, I would hide the difference between x86 and MAC.

  13. Slartie says:
    #5.1 2007-07-01 04:59 (Reply)

    Yes, the bitlib functions are working slightly different on a mac than on windows machines. Believe me, I too was surprised when I first saw that. I suppose it's because macs (as it seems even intel-based macs) are run in big endian mode. My bitmasking functionality went completely havoc on macs before I introduced that alternative path. Unfortunately I don't have access to a mac so I can't research this any further, but it's working fine with the current solution.

    Besides that, the lua bitlib functions internally work with 32bit integer numbers (confirmed that by looking at the source code myself), so using the shift functions like you suggested would break everything past the 32-bit-limit. That's why I emulate right shifts with divisions by some power of two (if that lua compiler is smart enough, it ends up as a shifting instruction anyway, but it's guaranteed to preserve the whole 52 bits of the mantissa).

    Because of this, I came to the conclusion that it's best to completely avoid using the bitlib functions because they don't seem to work equally on windows and mac machines and because they are silently limited to 32 bit. The only place I use one bitlib function is that bit.band in the MobMap_Mask function on windows, and the only reason I did not replace it with a modulo operator is because I know that there are no fields larger than 32 bit.


Add Comment


Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA 1CAPTCHA 2CAPTCHA 3CAPTCHA 4CAPTCHA 5