Testing String Equality Of Any Length Happens Instantly In ColdFusion
I was looking at someone's SQL error the other day when it turned out that the dude was trying to use a TEXT data field in a GROUP BY clause. This is not allowed (at least in SQL Server). I am not exactly sure why (either it's too costly or database structure is not built to grab text blobs on the fly?) but it got me thinking about comparing very large strings (such as the comparison that would be in a GROUP BY).
What happens when you compare a string of any length? Does the cost of the comparisons relate to the lengths of the strings in question? Let's see:
<!---
Store a large string which will then used to build an
even bigger string (FYI: I wrote this as a 300 word count
assignment in Creative Writing at Tufts).
--->
<cfsavecontent variable="strTextA">
She looked peaceful; eyes closed, head tilted down, breathing
- controlled and soft. Areas of fabric, turned dark with
sweat, stuck to her body revealing the grizzly figure below
it. Cut-off army fatigues could do little to hide her massive
and striated legs. Femininity with a warrior's touch.
Exhaling sharply, she opened her eyes and mounted the machine
next to her. With pads resting on her shoulders and white-
knuckled fists grabbing at the handles, she took one deep
breath, held it, then lifted the weight from its stack. Her
face, once soft and peaceful, was now plagued with pain. She
tried to control her body, which began to quake violently
beneath the load of five hundred extra pounds. At best, she
was able to stop her knees from buckling. She began to slowly
lower the heel of her foot down beyond the level of her toes.
Resting at the bottom for no more than a split second, she
groaned loudly and exploded upwards, flexing her engorged
calves as hard as she could. Back down and up, and again and
again. With every rep came the surfacing of a new vein, a
new ripple, new growth. Then, one the last rep, she held it
at the top, biting down, trying to fight the pain. And when
she could not hold it anymore, she collapsed. The iron
collided with its cradle as she collided with the floor.
There she lay, chest heaving, desperately trying to fill her
lungs. This time however, she did not try to control her
twitching legs. This time she smiled.
</cfsavecontent>
<!---
Repeat the above string 40 times. This will
generate a string that is 61,161, certainly a
hard string to compare???
--->
<cfset strTextA = RepeatString( strTextA, 40 ) />
<!--- Store a copy of A into B. --->
<cfset strTextB = strTextA />
<!---
Compare the two strings. Does this have to compare
every character? If so, it would be tens of thousands
of characters to compare.
--->
<cftimer
label="EQ Operator"
type="outline">
Equals: #(strTextA EQ strTextB)#
</cftimer>
Running the above code, we get:
Equals: YES
... and it runs in 0ms. That's instantaneous! So, what's going on? While I have not been educated in this formally, I believe that this is what the Hash code is for in all Java objects. As the string is constructed, the internal hash code of the string is updated. When one string is compared to the other, it must use this (instantaneous) rather than comparing every character.
To look into this a bit more, let's dump out the hash code before and after:
Pre Alteration:<br />
#strTextA.HashCode()#<br />
#strTextB.HashCode()#<br />
<!---
Alter both variables in such a way that the two
strings cannot be the same. I am using a RandRange()
here to ensure that the speed is NOT due to
compilation optimization of a static string.
--->
<cfset strTextA = (
strTextA &
ListGetAt( "A,a", RandRange( 1, 2 ) )
) />
<cfset strTextB = (
strTextB &
ListGetAt( "B,b", RandRange( 1, 2 ) )
) />
Post Alteration:<br />
#strTextA.HashCode()#<br />
#strTextB.HashCode()#<br />
This gives us the following output:
Pre Alteration:
-917390464
-917390464Post Alteration:
1625666753
1625666754
As you can see, prior to the final edit, both strings have the same hash code even though they are not the same object. Then, once the strings are slightly altered, the hash codes are slightly different (indicating that the strings do not contain the same value).
But remember, ColdFusion comparison is NOT case sensitive. In ColdFusion "Test" EQ "TEST" EQ "TeSt". In that case, strings that are not technically the same might still have the same ColdFusion equality. Let's see what the hash codes of two different case strings are:
#ToString( "ABCDEF" ).HashCode()#<br />
#ToString( "AbCdEf" ).HashCode()#<br />
This gives the us the following output:
1923910755
1953494211
Here, these two strings do not have the same hash code and yet:
Equals: #("ABCDEF" EQ "AbCdEf")#
... gives us:
Equals: YES
So obviously, there's something more than simple hash code comparisons going on. Also, a hash does not garuntee uniqueness. A hash value only guaruntees that two objects of the same value will have the same hash. So, after all this, I am still not sure how ColdFusion (on top of Java) does string comparison soooo freaking fast. I will just have to settle for the fact that ColdFusion is freakin-sweet!
I am sure this kind of stuff is covered on Day One of Java school, but this kind of stuff is fun for me to explore.
Want to use code from this post? Check out the license.
Reader Comments
I don't know if this applies or not, but I've noticed that in the times listed in the debugging information at the bottom of the page, that CF never reports a time between 0 and 10 ms. I assume it's because of the difficulty in measuring a period of time that small, but I don't know for sure. as such, any time I'm doing timed comparisons, I always wrap it in a loop of 1000 or more, depending on the resource intesity of the code. Might be an interesting experiment.
Yeah, I get the same thing. I have done what you are saying for other things (putting it in loops):
www.bennadel.com/index.cfm?dax=blog:236.view
But this string has sooo many characters that I felt that was not necessary.
Not to sure about this, but wouldn't comparing two identical long strings be more taxing if the pre-compiler didn't know that they were identical due to the copy immediately before?
I'm no expert on ColdFusion, but I know that many systems look for redundant code like this and simply replace it at runtime. Add a single letter to the end, do the comparison, then remove it, then do the comparion again.
The times should be identical (since the number of characters compared before something was realised), but if they aren't, something is doing some clever look-ahead. For instance, if the string length is held, a fast comparison would be to compare the length register, if there is one, before wasting time doing an actual compare. You'll see that because the time for the second comparison will be far faster than the other two.
(stumbled across this on google...)
Java string comparison actually uses a multi-step approach. The algorithm looks something like (in CFScript-ish pseudo-code):
function string_equals( o ) {
// check the type
if( o is not an instance of java.lang.String ) return false;
// check the length
if( o.length() != this.length ) return false;
// intern'ed strings are really the same instance, so do a reference
// equality check.
if( o == this ) return true;
// compare char by char
for( i=0; i < this.length(); i++ ) {
if( this.charAt(i) != o.charAt(i) ) return false;
}
return true;
}
Case-insensitive comparison is only different in the last step where it compares by char, but instead uses java.lang.Character#toUpperCase() or toLowerCase().
The equality check you're probably hitting is the reference check. That is, since both variables are references to the same String object in memory they must be equal, and there's no reason to even look at the chars. So it's O(1).
Comparing a string based on hashCode would actually be at least twice as expensive as the approach above because it wouldn't be able to abort right at the first non-matching char, instead it'd have the walk the entire length of both strings, and then compare the number after. And yeah, like you mentioned you'd still have to check every char because of the collision.
The actual implementation is available in the sun source (which I can't find online) or the GNU version is http://www.docjar.com/html/api/java/lang/String.java.html :)
@Elliott,
Good explanation. I love when stuff is designed so efficiently :)