Over the weekend I gave FNIStash a facelift to make it moderately more attractive. I’m pleased with the results!
You can see in the message box that some items are failing their parsing. Specifically, these are items that are sockets with gems or have augmentation abilities on them. Fixing those guys is my next task, and I’ve already made some strides in decoding the binary format for this information.
I ran into a big problem recently in FNIStash – I realized that it was using way more memory than I thought it should. What followed was a couple weeks of arduous investigation and learning about Haskell. If you find your program has a memory leak that is not due to thunks, these tips might help you out. Note that this all applies to the de facto standard compiler, GHC.
The first step to figuring out why your program is using a lot of memory is to measure it. You can enable profiling by compiling your program with the -prof and -rtsopts compilation flags. This enables profiling and allows you to control it from the RTS options passed from the command line when you run the program. For example,
MyProgram.exe +RTS -hy
will run the program and categorize memory usage by type. There are lots of categorization options available, such as by module or function.
When your program terminates, you’ll get a .hp file in the same directory as the executable. You can convert it to a viewable PS or PDF file using
hp2ps -e8in -c MyProgram.hp
ps2pdf MyProgram.ps
The result is something like this.
Memory profile of FNIStash categorize by type.
Here we can see that most of the memory is used up by ARR_WORDS, which is a backing type for ByteString and Text, among other things. Since FNIStash reads and parses an archive of binary files, this makes sense. However, the magnitude of the plot maxes out at around 25 MB. Why, then, does Windows report over 70 MB of memory used?
The discrepancy is due a couple of factors:
So if we discount the leaked memory, then we have 66 MB / 1.3 / 2 = 25 MB, which is right in line with what the graph reports. Turning off profiling saves an easy 30% of OS memory usage, but what if you want to save more? How can the memory leak be fixed? Are you stuck with using twice as much memory as necessary?
Fixing the memory leak was a Sisyphean process of changing data types, adding strictness, and other futile efforts until I found the magic bullet: the threaded run time system. By default, Haskell uses a single-threaded RTS (meaning 1 OS thread) that can nonetheless provide concurrency. Indeed, FNIStash uses multiple threads to run the frontend and backend separately. The -threaded flag enables the multi-threaded RTS (multiple OS threads), and using it completely obliterated the terrible memory creep I was seeing in the Task Manager. I don’t know why this is. My suspicion is that the idle-time GC that comes with -threaded more aggressively cleans up. Given the number of cores on modern machines, I plan to make this my standard in the future.
GHC enables the user to tune the garbage collector from the command line using RTS arguments. Here are the ones that I tested out. To use them, your program must be compiled with the -rtsopts flag. Additionally, and this is totally anecdotal on my part, it seems that having -prof enabled at the same time prevents any of these options from having an effect, so if you notice this you might want to compile without -prof.
In the end, I decided that killing the leak with the threaded RTS was enough for me. I don’t need extra memory savings by using -c for the moment. So I went from 70+ MB with a leak down to 48 MB with no leak by using -threaded and removing -prof. The real benefit, however, was learning more about GHC’s runtime system.
Here’s a brief update on the progress of FNIStash.
So something I had wondered about for a while has come to fruition: clockworkcore.org has already released an “infinite stash” program for Torchlight 2 called Stash Ninja. I learned about it a few weeks ago. This is hardly surprising to me, but I did wish that I would be the first. They released the first complete character editor and some other utilities, and their results are usually quite good. In fact, before I started FNIStash, I waited (and even emailed asking for an update) for CC to release the file specification under its Information section. At the time it said “Hopefully by the end of October,” which it still says today. I got tired of waiting for the file spec to come out, so I started to decode it myself, which was a long and tedious process. I’m pretty proud of all that I’ve accomplished on my own, but I have to admit that it looks like Chthon knows a little more about it than I do.
I still think my version (and the features I have planned for it) will have a lot to offer beyond what Stash Ninja does, if I ever get around to finishing it.
Here’s one such feature: searching based on item keywords, including stats, level requirements, etc. See it below, although the presentation needs a lot of cleanup. I’ve used sqlite to make an item registry database, and it has enough foreign keys to reuse data that it should be pretty scalable to many, many items. Enter in a few keywords, and the stash display is filtered to only show the items matching the query.
These three items are the only ones in the shared stash matching both keywords "poison" and "electric"
I pick at FNIStash off and on when I get a chance. Here’s what it looks like now. Each of the three tabs on the bottom is selectable to switch between the classes of items, and each item is individually drag and droppable. When you roll over an individual item, a description box pops up showing information about that item. There are still some things I need to put into the description box, but right now it works nicely as a proof of concept. What I want to eventually do is put the description box on the cursor like the game does.
A lot of cool news to report on FNIStash!
After successfully pulling png icons out of the TL2 game data, the next step was to get a GUI going. As I’ve written about previously, GUIs on Haskell (especially windows) are a PITA. However, after doing a clean reinstall of Haskell Platform, I was able to successfully install Ji and build the example executables.
The GUI landscape on Haskell is pretty bad. There are lots of frameworks out there, but actually installing them (much less using them) is often a big pain. There really hasn’t been much effort lately to make these frameworks more user friendly.
Where does Haskell get a lot of attention? The Web. Ji is a package that takes advantage of this web attention by turning your web browser into desktop GUI. You control the browser GUI from your Haskell application with commands to add elements, handle events, etc. Ji achieves this by running a Javascript library on your page that transparently communicates with the Haskell server using JSON to execute commands and send event notifications. The low latency of a desktop connection to itself makes this feasible, but technically Ji could be used for web apps that have a sufficiently fast connection (probably not a good idea, though). It’s all automatic and requires very little set up.
For FNIStash, I needed to expand on the Ji package by enabling assignment of element IDs and lookups thereof. I found that most of the infrastructure for this was already there but unused, which made adding the functionality pretty easy once I figured out how the package worked. The updates went into Ji earlier this morning, but Ji’s creator, Chris Done, has other things on his plate and wanted to unload responsibility for the package. Heinrich Apfelmus, of reactive-banana FRP fame, volunteered to take the project over with my assistance. That transition is still in the works.
I recently discovered how TL2 stores the location information for items. There is a hierarchical system of containers, slots, and indices, each of which has an ID to keep track of it all. From a raw item binary, I now know where that item is among TL2’s various item containers. The result?
A working shared stash display!
This is a working shared stash display, albeit unpolished. Each item is inserted into the emulated stash in its same position just like the game. The selection tabs at the top work, so clicking on a different tab changes the class of items that are displayed. Ji handles this all over the wire, although I admit is was a little tricky getting the click event handler written.
The error at the top indicates that there are some items in this shared stash file that I am not parsing correctly. It’s true that there are cases my parsing logic doesn’t currently handle, mainly because I don’t understand the file format entirely. For the time being, handling most cases is sufficient for moving development forward.
It’s actually starting to look like a real, genuine desktop app. I’m excited!
I recently got back to working on FNIStash in Haskell after some diversion into F#, and I had a great breakthrough in developing yesterday. I successfully installed the Codec-Image-Devil package of bindings to the DevIL image library, which I then used to read the DDS files that are archived in TL2’s PAK archive. For each one of these DDS files there also exists and IMAGESET (XML) file that defines the name and location of each icon in the DDS file. Using this information, I wrote out each icon to disk as a PNG file. My goal is that eventually these will be hosted through an HTML interface to simulate the TL2 stash.
I was somewhat selective about the icons I wrote to disk, and I still got out nearly 1000 icons. Here are a few:
In my last post, I wrote about my frustrations as a Haskell user on Windows. It led to a good discussion on Reddit about a number of points I raised, as well as some good comments on this site. I received more than one recommendation to try out F# as an alternative to Haskell. I’ve been casually exploring it for a few weeks now, and I have decided not to pursue it. My impressions are below. Keep in mind that I am coming to F# as a barely experienced Haskell user, but a Haskell user nonetheless. My impressions are also restricted to F# in Windows, as I did not investigate Mono or other Unix tools.
Full citizen status – Most immediately noticeable when coming to F# from Haskell is that Windows users come first. You do not need to install any Unixy tool chains to build what you want. In fact, almost everything you could possibly want is downloadable straight from Microsoft’s enormous and comprehensive .Net framework. Everything just works.
Documentation – Being part of the .Net framework, F# has a lot of corporate resources behind it at MS. This includes in depth documentation about nearly every .Net component. What is more, the .Net community is enormous, so finding examples online for pretty much anything is much easier than it is for Haskell.
Advanced tooling – One of the things Haskell suffers from, in my opinion, is lack of advanced development tools, including a standard and full-featured IDE. In F#, you get Visual Studio, a fully featured IDE that has been tested by thousands, if not millions. Haskell has no equivalent. Leksah is decent, but it is nowhere near as capable as VS.
For example, in F# on VS you can scroll over (almost) any value or function and see the inferred type signature for it. In Haskell, if I have a tough type error, I usually have to start explicitly defining the types of values and functions to narrow down the scope of my mistake. In VS, I can just scroll over the item in question and immediately get hints as to where I went wrong. Unfortunately, as far as I know this only works for named functions and not functions defined as symbols (operators).
Sane strings – Haskell’s default implementation of strings is a linked list of characters. While providing some advantages, in most cases it’s plain inefficient and unusable. GHC has some extensions to help fix this, such as the OverloadedStrings extension, and there are libraries to help as well, such as the text library. But different libraries choose to handle strings in different ways, so you often find yourself calling a number of conversion operations just to glue all the right types together. F#, on the other hand, has one standard string implementation that everyone uses.
Standards – Somewhat similar to the previous point, the Haskell ecosystem sometimes feels like the wild west, with different projects experimenting with types and strategies. Frequently, this can lead to ambiguity in how a newbie should approach a particular problem. In F#, there is usually a standard, recommended way to do things – the .Net way.
Computation expressions – This is a feature in F# similar to monads that is in some ways less powerful (see below) and in some ways more powerful. Like do notation, CE’s are syntactic sugar for monad-like operations. The familiar Bind and Return are present, like Haskell, but F# allows additional desugaring of loop expressions, the ability to implement lazy evaluation, and more.
No lazy evaluation (unless you want it) – Arguably a con overall, but my point here is that reasoning about performance and space usage is easier in F# due to strict evaluation semantics. The profiling utilities built into VS make this even easier still.
Verbose and odd syntax – A number of aspects of F# rub me the wrong way.
First, every declaration requires a let keyword. Let let let let let. Haskell in a lot of ways is much more concise because several values can be declared using one let.
Secondly (and this drives me nuts), F# function and type declarations must be made before the function is used. In Haskell, I often use a few helper functions that are defined down near the bottom of the file, but in F# those helpers must be defined near the top of else they can’t be used. Having such an antiquated restriction as this in a language a modern as F# boggles my mind.
Thirdly, the declaration of types and their constructors is sometimes not consistent. For instance, a constructed tuple in F# is (a,b) (like Haskell), but the type of this tuple is c * d. It’s not a hard thing to get over, but it does accentuate how self-consistent Haskell is.
No type classes! – I put an exclamation point on this one because it might be the single most important reason F# left a bad taste in my mouth. I did not realize the power of type classes until I tried to do functional programming without them. Take for example the monad type class. If a type is an instance of the monad type class, it is a given that it will work with replicateM, sequence, and a number of other functions that work on monads. If you have a new type, just declare a monad instance for it and sequence will work with it as well.
Trying to do this in F# is an exercise in frustration. There are ways to simulate type classes, but you have to do all kinds of inlining and type gymnastics to make the .Net CLR happy. Since it’s not readily supported by the language, there is no standard library of monad functions, and in a lot of situations you’ll have to reimplement these extraordinarily useful utilities yourself. This can lead to a good deal of code duplication. Just check out the FSharpx monad library code for examples.
Dependence on .Net – .Net is a comprehensive, full-featured framework, but it is huge and designed for OO languages. This results in classes like Stream, StreamReader, BinaryReader, TextReader, etc., which are all slight variations on each other. F# uses these same classes. Digging through the docs to find what you need can be challenge, but less so if you’re already familiar with .Net. In Haskell though, almost all of these can be replaced by mapping to/from a plain old byte string. Why does OO have so much seemingly unnecessary complexity to simply deserialize a type?
“Functional first” – F# is often described as a “functional first” language, meaning it supports both functional and OO programming paradigms. For some this is a plus (right tool for the right job and all that), but to me it seems like F# suffers from split personality disorder. Some of the F# libraries feel like little more than functional wrappers around an OO core. For a newbie, it’s not entire clear if these are merely measures of convenience or of necessity.
I doubt I was able to completely commit my thoughts on F# to this page, but this is at least a good start. I’ve decided to continue to wrestle with Haskell on Windows because even though the ecosystem is a house of cards, actually coding in Haskell is much more enjoyable than F#. I’ve started over with Haskell Platform to hopefully resolve as many compatibility issues as i can.
My progress on my current project (FNIStash) is unsteady, but yesterday I decided the time was right to start putting together a rudimentary GUI as both a learning exercise and as a boost of motivation for moving the program along. After working on getting a basic toy GUI for an entire day, I have absolutely nothing to show for it. It was truly the most disheartening and disappointing interaction with the Haskell ecosystem that I have had so far. Here are some of my impressions.
Trying to navigate the Haskell ecosystem as a Win 7 user is like making a deposit at a bank in loose change. Some banks will accommodate you and others will turn you away, but in either case you’ll get the feeling that the way you are doing things is fundamentally looked down upon. In cases where you are accommodated, you usually have to jump through many hoops, such as installing specialized build environments like MINGW32 or cygwin (which themselves might require several different installers) and manually building cross-platform libraries. After a lot of work, you’ll find you’re ready to install the package you wanted to install all along, only to have it break for who-knows-why. A lot of libraries are just not as easy as “cabal install haskell-gui-support”
Cabal is a frustratingly constraining tool. Far too frequently I encountered packages that, when trying to install, would say installing this package will break a dozen others. If not that, then I often would be notified that the dependencies could not be resolved. If you decide that you don’t care that your other packages break and go ahead with the install, it’s a tossup as to whether or not the install will be successful, but oops, you just broke a dozen of your old packages already, so if it fails you have some cleaning up to do. I’ve become pretty skilled at clearing out my cabal and ghc databases and invoking cabal install world to just bring my packages back to a self-consistent state after trying and failing to install a new package to explore.
For packages that leverage a cross platform library, this is frustraing but understandable. Often this house of cards is built by taking C or C++ source meant for a Unix like build environment, installing it through MINGw32 (as the special Windows installation instructions tell you to do), then installing a package from cabal that brings in the Haskell wrappers. It’s not pretty, but it’s kind of expected when pulling in functionality across platforms and across languages.
What I don’t understand is why cabal should ever have a problem with some packages breaking others or dependencies not being resolved. Cabal knows what package I want to install, it knows what versions of its dependencies it needs, and those dependencies are freely available from hackage (as are their own dependencies). You would think that this is a simple scenario with a straight forward solution – recurse and build all versions of everything as needed. But for some reason, cabal does not allow side-by-side installation of different versions of packages. If you have a package that requires a specific version of a dependency, you are effectively prevented from using any package that requires a different version. The utility cabal-dev is available, which allows the set of packages to be sandboxed on a per project basis, but that is small consolation if you (like me) need to get out of hell on a single project.
Side-by-side installation of multiple versions is a known and demonstrated solution to dependency hell. I alternate between blaming the community for not solving this problem and blaming myself for not understanding why it is so difficult. Solutions like Haskell Platform seem to me to be treating the symptom and not the disease.
The Haskell community is widely regarded as newb-friendly. If you need newb help, the haskell IRC channel is just a click away, and in cases where I didn’t get help from the IRC channel or haskell cafe, I’ve simply selected a knowledgable member of the Haskell subreddit and messaged them directly. No one has ever called me a newb or made me feel dumb for asking questions, even when the answer was staring me in the face in the docs and I just didn’t notice. It’s a great community.
What has happened (albeit occasionally) is that I might get no response at all, and as my questions become more advanced and specific, the likelihood that my queries get lost in the void increases. This is no different from any other language community. However, the Haskell community is tiny compared to, say, Python, so it’s pretty easy to exhaust all avenues of help. If you’re in the Haskell Windows community, it’s even smaller.
In my search to find a viable GUI package, the only one that I had absolutely any success with was HGamer3d, and it’s probably not a coincidence that it is designed to work on Windows. It was the only package that I was able to install successfully (without any headaches either), and it also had several example sources that worked effortlessly. The problem is that is has next to nothing for documentation. I tried modifying an example slightly only to have the executable fail on startup for unknown reasons. Maybe I will revisit it in the near future, but I would prefer to not have to learn Ogre to decipher the HGamer3d source code.
What I wanted at the start of all of this was a GUI library or framework that supported DDS texture files. By the end, I was willing to settle for anything that would successfully install and would display an image in any format. So why not the web frameworks? Yesod can’t resolve dependencies, happstack fails to load the network package (for which I found a work around online that, alas, doesn’t work), and snap fails to build the lens package due to a segfault in the generated code. I’m sure any of these would work if I had the “right” set of packages installed, but this is not a viable solution (see above). I can’t rip my environment apart every time I need something new.
wxHaskell is the most popular GUI toolset based on this reddit discussion, but I forgot to sacrifice a goat as step 0 of the installation process, so I had very little success with it.
I feel pretty similar to the author of this reddit discussion, except I had even less success. GLUT, GLFW, elm, reactive this, FRP that. I feel as if I have looked at everything and found success in nothing. Others work in Haskell GUIs all the time, so I know it is possible and that part of the blame lies on my side of the screen.
This experience has been a completely different kind of difficulty compared to learning the Haskell language. List comprehension, immutable variables, monads, type classes…these are all well documented concepts with essentially no variability from case to case. Read up long enough and eventually they click, and you are on your way. The problem I face now is that I don’t know where to go from here.
My last few posts have been about my hobbyist attempts at building a muling/looting application for Torchlight 2, akin to ATMA for Diablo 2. I call this application FNIStash. Well…I’ve made something of a big breakthrough in understanding how (most) of the item modifiers in the save file operate. Indeed, I now have the capability to take my shared stash file as input and generate the following as output:
GUID: 8940402106096732966
Full name: Beast Charm
Num Enchants: 0
Item level: 90
Used Sockets: 0/0
Dmg/Armor: 4294967295/111
Num elements: 0
Mods:+55.46508 Physical Damage
Gems:
GUID: -3941536332261843499
Full name: Commanding [ITEM] Forest Gauntlets
Num Enchants: 0
Item level: 44
Used Sockets: 0/0
Dmg/Armor: 4294967295/27
Num elements: 0
Mods:+15.0% pet and minion Damage
+15.0% pet and minion HealthGems:
GUID: 9067344113709864775
Full name: Shank’s Gloves
Num Enchants: 0
Item level: 48
Used Sockets: 0/1
Dmg/Armor: 4294967295/33
Num elements: 0
Mods:+34.199997 Ice Armor
+85.5 Fire Armor
+34.0 Dexterity Attribute bonusGems:
GUID: -3961984571336593215
Full name: Pocketwatch of the Tennant
Num Enchants: 0
Item level: 31
Used Sockets: 0/1
Dmg/Armor: 4294967295/0
Num elements: 0
Mods:+419.99997 Health
+4.5319996 Vitality Attribute bonus
+26.699999 Electric Armor
+26.699999 Fire Armor
+26.699999 Ice Armor
+26.699999 Poison ArmorGems:
A huge hurdle in building FNIStash as thus been overcome. There’s still a long way to go, but it’s really starting to take form.
In my previous post, I mentioned that I needed 95 MB of space memory just to run my simple test of extracting data from the Torchlight 2 PAK file. I did some investigating to figure out what the heck was going on. The culprit: using a FilePath (which is just a String) as the key to my map.
To profile in Haskell with GHC, you need to compile your program with the -prof option, and throw in -auto-all to automatically add cost centers to the profile output. You then execute the program with some additional flag to tell the runtime to collect profiling data. After that, you can look at the resulting .prof file for nice tabular data, but I prefer graphs. There are a few annoying steps to this whole process, so I created this batch script to handle most of it for me, which I named hprofile. It runs the exe, generates the products, and tags the prof and graph with a description.
@echo off
%2.exe %3 %4 %5 %6 %7 %8 %9
hp2ps -e8in -c "%2.hp"
DEL %2.hp
set ID=%~1
set newname=%2(%ID%)
IF EXIST "%newname%.prof" (DEL "%newname%.prof")
RENAME "%2.prof" "%newname%.prof"
IF EXIST "%newname%.ps" (DEL "%newname%.ps")
RENAME "%2.ps" "%newname%.ps"
DEL "%2.aux"
CALL ps2pdf "%newname%.ps"
DEL "%newname%.ps"
Here’s the graph resulting from
>hprofile "baseline" FNIStash-Debug +RTS -p -hc
Memory usage for String keys in Map
The forText2/pakFileList is the function that generates the keys in the Map. In this case, the keys are Strings (FilePaths).
I changed the type of the key in the map from FilePath to Text. This actually made a lot of sense since I parsed them out as Text anyway, but chose FilePath before so I could use the path handling utilities in System.FilePath. The lookup function on the map still takes a FilePath as the key. Now, however, the FilePath is converted to Text within the lookup function. Here is the result.
Memory usage for Text keys in Map
No more runaway memory usage! The moral of the story: avoid String.