Ayende @ Rahien

Refunds available at head office

The operation was successful, but the patient is still dead… deferring the obvious doesn’t work

So, I have a problem with the profiler. At the root of things, the profiler is managing a bunch of strings (SQL statements, stack traces, alerts, etc). When you start pouring large amount of information into the profiler, the number of strings that it is going to keep in memory is going to increase, until you get to say hello to OutOfMemoryException.

During my attempt to resolve this issue, I figured out that string interning was likely to be the most efficient way to resolve my problem. After all, most of the strings that I have to display are repetitive. String interning has one problem, it exists forever. I spent a few minutes creating a garbage collectible method of doing string interning. In my first test, which was focused on just interning stack traces, I was able to reduce memory consumption by 50% (about 800Mb, post GC) and it is fully garbage collectible, so it won’t hung around forever.

Sounds good, right?

Well, not really. While it is an interesting thought experiment, using interning is a great way of handling things, but it only mask the problem, and that only for a short amount of time. The problem is still an open ended set of data that I need to deal with, and while there are a whole bunch of stuff that I can do to delay the inevitable, defeat is pretty much ensured. The proper way of doing that is not trying to use hacks to reduce memory usage, but to deal with the root cause, keeping everything in memory.

Comments

Szymon Kulec
12/26/2009 11:55 AM by
Szymon Kulec

Hi Ayende,

will you end up with a db for your profiler?

Cengiz Han
12/26/2009 12:47 PM by
Cengiz Han

You can provide an option for your tools like "use mmf" and if users encounter with OOME exceptions can try to work in mmf mode.

http://mmf.codeplex.com/ you can check this project (memory mapped files)

and also .net 4.0 has system.io. memorymappedfiles namespace for this kind of job.

btw. luckly, I didn't need to use this projects for now.

FallenGameR
12/26/2009 07:57 PM by
FallenGameR

When OS runs out of memory it swaps.

Either you make some sort of clustering (main string + differences) or you swap memory to disk.

Jeff Brown
12/27/2009 06:14 AM by
Jeff Brown

Now wondering whether the next series of posts will feature disk based index shards and external sorting...

Or perhaps it will be about creating summaries...

Patrick Smacchia
12/27/2009 07:49 PM by
Patrick Smacchia

Just an idea that would take a bit of CPU cycles but can drastically reduce memory. In a code base, just a relatively small set of word is used in code elements identifiers. (Do, Go, String, Session, Event, On, Profile, Handler, get_, (, ), User...). You can harness that fact to your advantage by building a set of these words on the fly and a string identifier becomes an array of ids of these words.

Another idea: store strings using UTF8, since 99% of char in identifiers are in the first 128 ASCII chars (and take only one byte footprint instead of two).

Recently I applied several others tricky-like algo in NDepend with incredible performance/mem consumption improvements. What I discovered in 2009 is that using very tricky ideas, I never heard about in 15 years of programming, pays off. The result is to be released in a few weeks, I cannot wait :o)

Ayende Rahien
12/27/2009 08:15 PM by
Ayende Rahien

Patick,

That is more or less what I meant by interning strings.

As for UTF8, it doesn't work if you need to translate to standard strings all the time, you would allocate a lot of mem just that way

Patrick Smacchia
12/27/2009 09:55 PM by
Patrick Smacchia

The problem is to keep many string values alive (i.e not collectable by GC) in memory, so you need a way to compress/uncompress strings values (with a set of words or UTF8 or anything else).

String interning is not really compression in the sense that you keep the whole strings values in memory. Strings interning just avoid duplication of same values. Moreover, string interning is not computation free, computing hash code on strings + dico search is not free and even, proposed string hash code impl in .NET Fx are far from being optimal in terms of performance.

I think you need something more tricky than string interning to save some memory.

As for UTF8, it doesn't work if you need to translate to standard strings all the time

I don't get you, once you need a string value, just uncompress it, use it, and immediately release the reference?!

Ayende Rahien
12/28/2009 05:00 AM by
Ayende Rahien

Patrick,

You are correct, in a sense.

The problem is that uncompressing a string will require me to allocate more memory, which leads to the GC having to do more work in the end.

My main worry isn't CPU time, it is memory, and having to keep allocating new strings (by the millions, btw) leads to a lod of garbage that the GC have to clean up.

Patrick Smacchia
12/28/2009 07:56 AM by
Patrick Smacchia

Are you sure that you can overwhel the GC this way? Internally the GC has its own heap for string and is extremely optimized to allocate/deallocate many strings. When it comes to performance and GC, common sense and suppositions are of poor help. Code it, measure it, and see where is the bottleneck, if any. Many times I had good surprises. And when I had bad surpirses, they never came from where I expected.

Ayende Rahien
12/28/2009 11:30 AM by
Ayende Rahien

Patrick,

I am speaking out of experience here, I just finished doing MAJOR perf session on the profiler.

Patrick Smacchia
12/28/2009 11:46 AM by
Patrick Smacchia

I am surprised that your program overwhelm the GC by allocating short-living strings. Certainly the GC team would be interested by your experience.

I am not sure to understand, what is the content of your strings, code element names? profiler events descripion?

Ayende Rahien
12/28/2009 12:06 PM by
Ayende Rahien

Patrick,

They aren't short lived, they go, almost always as-is, to live as part of the in memory model

Ayende Rahien
12/28/2009 12:07 PM by
Ayende Rahien

Sorry, what I meant, is that they aren't short lived, they are put into a processing queue and it may be quite a while until they are processed and some of them discarded

Comments have been closed on this topic.