Skip to main content
Ben Nadel at InVision In Real Life (IRL) 2019 (Phoenix, AZ) with: Jeanette Silvas
Ben Nadel at InVision In Real Life (IRL) 2019 (Phoenix, AZ) with: Jeanette Silvas

Testing String Equality Of Any Length Happens Instantly In ColdFusion

By
Published in Comments (5)

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
-917390464

Post 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

4 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.

1 Comments

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.

132 Comments

(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 :)

I believe in love. I believe in compassion. I believe in human rights. I believe that we can afford to give more of these gifts to the world around us because it costs us nothing to be decent and kind and understanding. And, I want you to know that when you land on this site, you are accepted for who you are, no matter how you identify, what truths you live, or whatever kind of goofy shit makes you feel alive! Rock on with your bad self!
Ben Nadel