FNIStash r1.0 released!

It’s been a long time coming, but I have made the first release of FNIStash!  I consider this release experimental until all the bugs are worked out.  So far I have already received some good feedback and a couple of bug/compatibility reports.  Follow the links below for more.

FNIStash homepage, with video tutorial

Announcement of FNIStash on Runic Games Forum

Announcement of FNIStash on r/Torchlight subreddit

It was a long, educational experience writing this program.  I think I got a good feel for Haskell and hope my next project with the language focuses more on good habits and style instead of focusing almost solely on making a functional product.  I’d like to eventually write up a post-mortem of my experience of building a non-trivial application in Haskell as a 100% FP and Haskell newb, so look for that in the future if you’re interested.

FNIStash nearing completion

I’ve been able to get some decent time working on FNIStash lately, and have made some really good strides.  It’s nearing feature completion, as least as far as the major features I have in mind are concerned.  Preliminary testing between my wonderful fiancee and myself will hopefully root out any sneaky bugs or deficiencies.  Here’s what it looks like now.

Final look of FNIStash? Perhaps.

Final look of FNIStash? Perhaps.

Managing Items

When FNIStash reads the shared stash file, it registers all items it finds in a database.  The new Registry table shows the status of all registered items.  If the item is Stashed, then it is currently in the shared stash file.  Other statuses are Inserted (inserted into an item) and Archived (existing in the database only).  Another status I want to add is Lost or something along those lines, which would describe items that used to be Stashed but somehow left the stash, such as when they get traded away or put on a character.

The Registry table also serves as the drop target for moving items from the Stash to the Archive.  Drag and drop an item to the table, and the item disappears from the stash and its status becomes Archived.  Once archived, the appropriate row text in the table changes color to black, and the row’s icon becomes draggable to allow the user to drag the item from the Archive to insert it back into the stash.  For convenience, the yellow arrow button will automatically archive all items in the stash.

The UI mechanics here are quite close to what I imagined when I started this project.  I’m really happy that threepenny-gui, the Haskell GUI library I’ve been helping to test and sometimes develop, has been able to keep up.

Finding Items

The Filter field at the top of the UI allows the user to find items by key phrase(s).  Stashed items not matching the phrase become faded, and any row of the Registry table whose item doesn’t match the phrase is also hidden.

The keyword filter allows easy searching of items.

The keyword filter allows easy searching of items.

Capturing the Grail

One of the key achievements in any hack and slash game is achievement of the grail – finding at least one of each item in the entire game.  Normally, the limited stash capacity of these games makes searching for the grail really inconvenient, sometimes prohibitively.  FNIStash helps grail searchers by automatically keeping track of how much of the grail has been registered in the database, as well as which items still need to be found and how rare they are.  I still have some work to do to properly exclude items that are in the game’s files but not actually obtainable, but the basic report format is shown below.

Early version of FNIStash grail report.

Early version of FNIStash grail report.

What’s Next

With a little luck, I’ll be able to start testing in earnest in the next few weeks!  One thing I’m concerned about is how TPG and the database will hold up when the number of registered items gets into the several thousands.

Item display in FNIStash

I’ve spent the last week or so digging down into the Torchlight 2 data files and enhancing the item display popup for FNIStash.  Now it’s a quite acceptable emulation of the item popup found in the game, although for some items there are still some quirks.

Item popup for FNIStash.

Item popup for FNIStash.

FNIStash gets a facelift

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.

FNIStash GUI revamp

 

Improving memory performance in Haskell programs

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.

Understanding memory usage

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.

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?

Memory footprint of FNIStash

The discrepancy is due a couple of factors:

  1. First, the profiling doesn’t come for free.  Compiling with the -prof option necessitates more memory just for reporting purposes.  This requires approximately 30% more memory than usual.  This overhead isn’t reported on the plot, but the OS sees it.
  2. The reported memory usage is only “live memory.”  It doesn’t include old data that has not been collected by the garbage collector yet.  In fact, in very loose terms, the default GHC GC waits until live data grows to the size of old data before collecting it.  This means your program might use twice as much memory as needed.  Note that when the garbage collector does run, it temporarily needs more space to reorganize the live data, so if a large amount of data is being collected at once, you can see memory usage (as reported by the OS) spike up.
  3. FNIStash, in particular, has some kind of memory leak.  Right after start up, the OS memory usage was around 66 MB, but crept up to 70 MB after some minor GUI interaction.  It’s actually unclear to me whether the leaked memory is reported in the plot.

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 leak

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.

Tuning the garbage collector

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.

  • -c : This option changes the GC algorithm to use a slower compacting strategy instead of a copying strategy.  What I think this mean is that instead of copying bytes around the heap when running GC, data gets compacted near where it already is.  The end result is less heap usage.  In my case, using this option yielded savings of around 10%.
  • -Ffactor : Here “factor” is a value.  By default, GHC uses a value of 2.  This is the growth factor allowed before GC is run.  If you make this smaller, GC will be run more often.  However, this didn’t seem to help me out much.
  • -Gx : If x = 1, this enables the single generation collector.  I used this option without any others, and it actually increased my memory usage considerably and made my program much slower.  I also tried G3, but that used a lot more memory as well.

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.

Item filtering in FNIStash

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.

Image of filtering in action

These three items are the only ones in the shared stash matching both keywords "poison" and "electric"

FNIStash GUI progress

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.

Progress pic for FNIStash GUI

Emulation of TL2 Shared Stash

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.

What is Ji?

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.

Ok, so FNIStash…

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?

Image of working shared stash emulation

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!

Success in Extracting TL2 Icons

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:

A comparison of Haskell vs F#

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.

F# – The Good

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.

F# – The Bad

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.

Back to Haskell

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.