String Interning and Thread Locking

  • Thread starter Thread starter Chris Mullins
  • Start date Start date
C

Chris Mullins

I've spent some time recently looking into optimizing some memory usage in
our products. Much of this was doing through the use of string Interning. I
spent the time and checked numbers in both x86 and x64, and have published
the results here:
http://www.coversant.com/dotnetnuke/Default.aspx?tabid=88&EntryID=24

The benefits for our SoapBox suite of products are pretty compelling, memory
wise.

Before I roll the changes into our products, I have a very real concern:

The Intern Pool is (according to Richter) Process wide, and therefore shared
by any number of AppDomains. By implication, this also means all the threads
in the process share a single intern pool.

Our products are very heavily multi-threaded and I'm worried that accessing
the Intern Pool from a number of threads is going to introduce signifigant
locking that I don't have any control over.

Does anyone know what locking algorithms the Intern pool is using? Is it
Monitor semantics, Reader-Writer Lock semantics, or (I hope not) a remoting
construct to all cross appdomain synchronization?

I don't have any visability into the Intern pool, and without that
visability I'm very hesitant to use it. I poked around with Reflector, but
it ends up in an Internal Call method pretty quickly.
 
Hi Chris,

There's a good chance that you can see for yourself in our shared source
release
(http://www.microsoft.com/downloads/...61-3F26-4555-AE17-3121B4F51D4D&displaylang=en)
by following that internal call or just searching for a string literal
implementation.

If we don't provide the implementation, I encourage you to write a
multi-threaded test with a representative number of readers and writers. I
believe you will find things very performant, and to check you could compare
against your own implementation of any of those locking schemes.

Hope this helps,
Dave
 
My issue is that there's no guarantee the Shared Source implementation, and
the production .Net implementation are the same.

Likewise, unless it's documented somewhere in the ECMA standards, there's no
guarantee it won't change out from under me.

Rather than relying on the built-in string interning, I'm just using a
custom implementation. This will also allow me to sweep the intern table
from time to time, and remove unused strings. In a long running server
process, the idea of a string table that grows without bounds and provides
no mechanism for removing values just doesn't have very much appeal.
 
Chris,

I'm certainly not an expert at the internal workings of the CLR, but if
I were absolutely forced to make a guess I would say that the intern
pool probably uses some sort of very fast low-lock (or even lock-free)
hashtable implementation. Though, a monitor like implementation seems
reasonable. I think a reader-writer lock would be terribly slow in
this situation since the operation is not bound to IO or other blocking
resource. A remoting construct seems unlikely since the call quickly
dives into the internal CLR code wher it's not unreasonable to think
the standard AppDomain access rules do not apply.

Brian
 
Hi Brian,

I'm curious, what makes you think about the lock constructs that way?

For example, in a number of cases, lock-free is slower than locking. It's
only under certain conditions that these two reverse roles, and lock-free
becomes the quicker of the two.

Also, I'm curious as to why you thin reader-writer lock would be slower than
a monitor? There's nothing inheriently I/O related to the reader-writer lock
that I know of. For an intern pool, I would imagine 90%+ of the operations
would be reads against a hashtable of some sort - which would imply a
reader-writer lock as an applicable algorithm. What here am I missing?

I agree with your assessment of "standard AppDomain access rules do not
apply", but it's always good to know for sure.

--
Chris Mullins

Brian Gideon said:
Chris,

I'm certainly not an expert at the internal workings of the CLR, but if
I were absolutely forced to make a guess I would say that the intern
pool probably uses some sort of very fast low-lock (or even lock-free)
hashtable implementation. Though, a monitor like implementation seems
reasonable. I think a reader-writer lock would be terribly slow in
this situation since the operation is not bound to IO or other blocking
resource. A remoting construct seems unlikely since the call quickly
dives into the internal CLR code wher it's not unreasonable to think
the standard AppDomain access rules do not apply.

Brian
Click to expand...
 
Chris,

Honestly, it's nothing more than a guess. And I'm more than willing to
be very wrong about it.

You bring up a good point that low-lock strategies can be slower in
some scenarios. I hadn't originally considered that.

Similarly, the reader-writer lock would only be faster in some
scenarios as well. It's been my experience (admittedly limited) that
reader-writer locks work best in scenarios where the critical section
spends some time in a wait state. In the case of the intern pool I
would be surprised if a reader-writer lock were faster than a monitor
even if reads outnumbered writes 10 to 1. It might be beneficial for
me to reexamine the ReaderWriterLock and compare it against the Monitor
to see what scenarios it performs better and what the break even point
is.

Brian
 
Back
Top