Mike Klaas schrieb:

...

cause problems for other users of the interned string. I agree with the reasoning, but propose a different solution: when interning an instance of a string subtype, PyString_InternInPlace could simply intern a copy.

Interning currently requires an external reference to prevent garbage collection (I believe). What will hold a reference to the string copy?

For PyString_InternInPlace, the caller will receive a reference; the original object passed in is decref'ed. A typical caller of PyString_InternInPlace will just store the reference in some global/static variable. builtin_intern will return it to the caller, which then needs to store it. This was always the case with intern(); the usage pattern is foo = intern(foo) as intern may return a different object (e.g. if the string was already interned). Regards, Martin

Greg Ewing schrieb:

That doesn't quite give you everything that real interning does, though. The string comparison method knows when both strings are interned, so it can compare them quickly whether they are equal or not.

No, it doesn't - see stringobject.c:string_richcompare. If they are identical, they are quickly recognized as equal, and as not not-equal. Otherwise, if eq comparison is requested, it compares the size, then the first characters, then does memcmp - so if they are unequal, it doesn't help that they are both interned. If comparison is for notequal, no special casing is performed at all (except that knowing that identical strings aren't notequal). The entire algorithm and optimization works just as fine for a user-defined interning dictionary (assuming that all relevant strings get into it). Regards, Martin

Greg Ewing schrieb:

It's certainly possible to tell very easily whether a string is interned -- there's a PyString_CHECK_INTERNED macro that tests a field in the string object header. But, I can't find anywhere that it's used in the core, apart from the interning code itself and the string alloc/dealloc code.

Can anyone shed any light on this? It seems to me that by not using this information, only half the benefit of interning is being achieved.

You seem to assume that checking this property would improve performance. I find that questionable; as always with performance and optimization, one cannot know until it has been benchmarked. My guess is that - the cases you want to cover are comparably infrequent (compared to the total number of richcompare invocations) - checking the additional field always may cause a performance loss, not a performance gain, because of the additional tests. If you want to sure, you need to make some measurements (e.g: what is the percentage of EQ and NE invocations, in how many cases are both strings interned, and in what percentage of these cases are they not the same string). Regards, Martin

Larry Hastings schrieb:

If I understand your question correctly, you're saying "why doesn't string comparison take advantage of interned strings?" If so, the answer is "it does". Examine string_richcompare() in stringobject.c, and PyUnicode_compare() in unicodeobject.c. Both functions compare the pointers of the two objects in case they are literally the same object, and if so skip all the expensive comparison code. Interned strings which have the same value are likely to be (are guaranteed to be?) the same object. And there you are.

If that's not the question you are asking, I'll be quiet, 'cause it seems like other people understand what you're talking about.

The question was similar: "Why doesn't it take the maximum advantage?" Interned strings that are equal are guaranteed to be identical. So if strings are not identical and both interned, it could infer that they can't be equal, but currently doesn't infer so (instead, it compares length and contents in this case). Regards, Martin

Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:

Josiah Carlson wrote:

...

def intern(st): ...

If I remember the implementation of intern correctly, that's more or less what happens under the covers.

That doesn't quite give you everything that real interning does, though. The string comparison method knows when both strings are interned, so it can compare them quickly whether they are equal or not. Your version could detect equal strings quickly, but not unequal strings.

Assuming that dictionaries and the hash algorithm for strings is not hopelessly broken, I believe that one discovers quite quickly when two strings are not equal. Simple testing seems to confirm this, but I didn't work too hard to disprove it either. - Josiah

Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:

Josiah Carlson wrote:

...

Assuming that dictionaries and the hash algorithm for strings is not hopelessly broken, I believe that one discovers quite quickly when two strings are not equal.

You're probably right, since if there's a hash collision, the colliding strings probably differ in the first char or two.

Interning will speed up the case where they are equal, where otherwise you would have to examine every character.

Except that the scanning of the data needs to happen at some point anyways. You first allocate the new string, copy the data into it, compare the content against something in the interned dictionary, and if there is a match, deallocate the new object and return the interned object, otherwise return the new object. This is also the case when one uses the "just give me a string, I'll fill in the data myself" for more or less user-implemented things like ''.join(lst).

Still, there could be extension modules out there somewhere that make use of PyString_CHECK_INTERNED, so there's a slight chance that home-grown interning might not give the same results in all cases.

Perhaps. I just never intern. I've found that I'm much happier assuming that the Python runtime will do good enough. - Josiah

Hrvoje Nikšić schrieb:

Another reason is that Python's interning mechanism is much better than such a simple implementation: it stores the interned state directly in the PyString_Object structure, so you can find out that a string is already interned without looking it up in the dictionary. This information can (and is) used by both Python core and by C extensions. Another advantage is that, as of recently, interned strings can be garbage collected, which is typically not true of simple replacements (although it could probably be emulated by using weak references, it's not trivial.)

OTOH, in an application that needs unique strings, you normally know what the scope is (i.e. where the strings come from, and when they aren't used anymore). For example, in XML parsing, pyexpat supports an interning dictionary. It puts all element and attribute names into (but not element content, which typically isn't likely to be repeated). It starts with a fresh dictionary before parsing starts, and releases the dictionary when parsing is done. Regards, Martin