switching with 2 variables

[Sep102]

Well, it's not necessarily an inadequacy, it could very well be a design decision. Say there's one intern table shared by everything running under the CLR, now you need some way to clean up only the strings that were interned by the application that is currently being unloaded.

The application could have a list of indices into the table that it iterates through and decrements a reference count in the intern table for each of those entries and deallocate any that have no more references.

Of course, thinking about it, we could also extend this to, say threads. Why shouldn't the intern table be cleaned after a thread exits and all of it's interned strings removed?

That's all just conjecture though, there's probably a good reason why it's done this way that I just don't know about, probably performance though. It might be worth a look to see if the .NET Compact Framework handles interned strings differently to see if it was a conscious design decision for the general .NET Framework to have semantics that may waste some memory but will end up being quicker.

[Courageous]

That's one of the things I don't understand. In the large, string internalization compacts memory, because instead of using the number of bytes in the string each time it is instanced, you get a pointer to a lexigraphically identical string.

I guess this is as obviously compact on 64 bit systems as it is on 32 bit ones, but be that as it may...

C//

p.s. have implemented string internalization tables myself, for special projects.

[Sep102]

Originally Posted by Courageous

That's one of the things I don't understand. In the large, string internalization compacts memory, because instead of using the number of bytes in the string each time it is instanced, you get a pointer to a lexigraphically identical string.

I guess this is as obviously compact on 64 bit systems as it is on 32 bit ones, but be that as it may...

C//

p.s. have implemented string internalization tables myself, for special projects.

As interning pertains to commonly used strings, I don't disagree with you at all Courageous, I agree completely, interning can produce a great increase in the efficiency of both memory usage and certain computations involving the instances.

What the main problem stems from is either the automatic interning of strings or the reckless interning of strings (essentially one in the same). This is where string interning fails, since there may very well be thousands of strings in the intern table that have only been used once and will never be used again, yet they still are present (unless of course some kind of caching and weak reference system was used, but that's another topic) until at least the end of the application. And those could just be the strings that were blatantly created in the program, also stored in the table would be all strings resulting from operations on a string (one such example I could think of was profiling operations, such as ("Running time: " + msRan + " ms"), now, likely, every time would represent a different entry in the table).

Also, although string internalization can greatly help lower the memory usage of your application, even judicious usage could potentially hamper you. For example, say that my application interns 100 kilobytes worth of strings that it uses commonly throughout the program. I now have an extra 100 kilobytes of memory added on to my working set at all times. Also, consider if at any one time I was only using five percent of the strings in the table. Normally only 5 kilobytes would need to be present in memory at a time, since the garbage collector would have cleaned up the rest when the program was not using them and reallocated them when they were needed again, now all of the data must constantly reside in memory for at least the life of the application. Essentially, my concerns boil down to the fact that doing this seems to tread on the ground that the GC is best at walking and saying that you will be doing a better job than it, at least in this instance (of which I have no problem with, just so long as it's done carefully and is backed up with statistics confirming the reasoning used, and, of course, this is really only true if this is done solely in the name of memory conservation and efficiency and not, for instance, for string comparison efficiency gains or some other advantage interning offers).


Given all this, I've reached the same conclusion I had before, all things in moderation, lest they be misused through unintentional overuse. String interning suffers from the same caveats as any other feature and, just like everything else, needs to be used judiciously and have logic backing up the reasons for its use.

[Sep102]

Also, if you, like me, happen to be interested in tidbits about the performance of various parts of the .NET Framework, I highly suggest reading the weblogs of the Microsoft .NET performance team. Rico Mariani's, for example has a lot of interesting things in the articles (it's also the only one I currently have as an RSS feed on my main screen, which is why it gets a link).

[Courageous]

What the main problem stems from is either the automatic interning of strings or the reckless interning of strings (essentially one in the same).

A fair comment. Certain patterns of use, however, yield good information to the interpreter about the probable use of a string. One might argue, for example, that any string that goes into a dictionary, be it as a key, or as a value regardless, should be interned as a matter of course. And so forth.

C//

[Sep102]

Originally Posted by Courageous

What the main problem stems from is either the automatic interning of strings or the reckless interning of strings (essentially one in the same).

A fair comment. Certain patterns of use, however, yield good information to the interpreter about the probable use of a string. One might argue, for example, that any string that goes into a dictionary, be it as a key, or as a value regardless, should be interned as a matter of course. And so forth.

C//

Heh, thought I covered that in my "judicious use" statement or "commonly used strings". That is, I agree with you for the same reason I did before. A good argument could very well be made as to why that is a valid use of interning, as there is a good chance the string will be used and a decent chance that it will be used often, thus a good use of string interning to cut down on both memory usage and time spent doing comparisons.

Like I, thought, I guess, I said was that usage of interning, just like pretty much everything else needs to be determined on a case by case basis and can't really just be applied as a general rule for everything.

[Courageous]

Well I was just saying that for a dictionary, the runtime itself could make the decision to intern. And a variety of other similar cases.

C//

[noobie]

I dont see a point why it should be interned if it is used in a dictionary. If it is a key, probably there wont be many of it. and for the comparison part, it uses a hash method and doesnt compare the exact string with anything..

It is not good to have a default internalization behaviour. It is best that it would be up to you..

[Courageous]

People put thing into dictionaries to look thing up. Since this is the essential purpose of a dictionary, the fact of entering something into it is a major clue to its use. Items entered as keys into dictionaries have to be matched on a dictionary lookup (as a final part of the hashing cycle one must test for definite match). Internalization makes matching a string one or two instructions only. I should hope you should see the probabilistic nature of this benefit. I.e., "quite likely to be beneficial... to the point of being certain."

BTW, if you don't like the fuzzy nature of "quite likely to be beneficial," you should step out of the use of C# dictionaries altogether, and proceed to something like a red-black tree, as the fundamental algorithm that the dictionary is implemented with (typically, and specifically in C#) is itself one that is statistical and not at all certain. FYI.

C//

[noobie]

You might have millions of items in a hashtable, but that doesnt mean necessarily you will look for every one of them. And actually it would be pointless to use interned strings to speed up the program in such a case because speed increase is neglectable.

btw, why do you think dictionaries/hashtables are implemented as RBT? Because they are not..

[Courageous]

noobie,

Several of your posts have illustrated that when you reply to my posts, what you need to do is read them more carefully first.

For example, I never said that dictionaries/hashtables are implemented as RBT, that's your invention.

Your prior remark that it does not compare the exact string is mistaken, unless you happen to believe that C# hashtables use heavy hashing, like MD5, without a match test, which I highly doubt.


C//

[noobie]

Well, actually it does compare, but it uses Equals method which does a value comparison, it doesnt even check references. even it did check references, it is an already O(1) algorithm and trying to make it faster in "this way" is just pointless.

[Courageous]

Well, actually it does compare, but it uses Equals method which does a value comparison, ...

I knew this. You didn't. But this didn't keep you from lecturing to the contrary. Why?

...it doesnt even check references. even it did check references, it is an already O(1) algorithm and trying to make it faster in "this way" is just pointless.

"Actually" hash tables are average case O(1), but are worst case O(N). In strict complexity theory, the O() notation that you are invoking ala abracadabra is to express the upper bounds of the compute algorithm. So to use it without mentioning the important word "average" is strictly incorrect. O(N) is correct.

But more pragmatically, in the linear hashing's average case, it is more technically expressed O(1)+K, where K can be large, and improving the performance of the hash table (that persnickety and annoying K you dismiss as irrelevant) can have a substantial runtime percentage change on many applications.

To dismiss pragmatic application runtime, all hand waivey hand waivey like, is not the least bit wise. I have seen applications that use algorithms with better theoretical performance get destroyed by applications with better pragmatics. Theoreticals aren't everything.

An extensive performance test which I have performed recently suggests to me rather strongly that C# hash tables "actually" do in fact intern their strings. Or so it would appear, without exceptional explanation to the contrary.

C//

[noobie]

I know all that hashtable stuff but still I cant see any valid point you have taken. I didnt say it wont do any good for performance, yes it will but it is neglectable.

-Lets say the algorithm (which is actually in worst case..your are right) O(N), it would be much pointless to do internalization.
-Lets say its O(1)+K and K is too large. Do you really think getting rid of just one simple Equals method would make it much faster? I mean is it worth to effort? The true answer is No.

Besides there is a good chance of the hashtable would be a temporary, using default internalization would not be a good idea.

C, I dont know what tests you have done but hashtables doesnt use internalization. actually it doesnt know even if the key is a string. (It is what the reflector says)

And appearantly, this debate is not going somewhere. So lets just drop it..

[Courageous]

Do you really think getting rid of just one simple Equals method would make it much faster?

It prevents as many instructions as the string has length, for the final match test (which is, indeed necessary). As for the test performed, I'll leave it to your imagination.

C//

[arul]

Originally Posted by Courageous

In strict complexity theory, the O() notation that you are invoking ala abracadabra is to express the upper bounds of the compute algorithm.

Sig-worthy

Anyway, there's a nice article about undocumented features of strings over at CodeProject, especially the part called 'Efficient String Switches' in the middle of the page.

Strings UNDOCUMENTED.

[yarex]

If you want speed, go for if-es, they are always faster then switch.

If you want even more speed, use unsafe code .