Relative CFLoop Performance for Various Loop Structures
Posted by Eric in ColdFusion, Programming on May 21st, 2008
Introduction
Jim over at Ben Nadel’s blog made the assertion that looping a list is faster than looping a struct. It’s an interesting assertion that looping a list would be faster than looping an array. I did a test of my own to find out.
Setup
Starting with objects with 1 entry populated, I increased the number of populated entries by 1,000 until I reached 100,001 entries in each of an Array, a List, and a Struct.
I also compared the following syntaxes:
<cfloop array=”myArray” index=”x”>
<cfloop from=”1″ to=”#ArrayLen(myArray)#” index=”x”>
<cfloop collection=”#myStruct#” item=”x”>
<cfloop from=”1″ to=”#StructCount(myStruct)#” index=”x”>
<cfloop list=”myList” index=”x”>
<cfloop from=”1″ to=”#ListLen(myList)#” index=”x”>
For each type of test, I did a <cfsavecontent> to cfoutput the relevant entries from each object without causing a ton of data to be sent back to the browser. The actual <cfloop> and output was tight (all on one line to minimize the total content going to cfsavecontent).
I ran each incremental test 10 times to get an average duration. I did this because my in my earliest tests it was obvious that garbage collection was causing significant variance (shorter tests often took longer than their longer brethren). Even still it’s obvious garbage collection played a bigger factor in efficiency than the actual test results, making them somewhat difficult to decipher meaningfully.
Execution
Early on, I dropped the final test (which involved ListGetAt() for the output portion) since while the others were still taking a few milliseconds, this test was already taking multiple seconds.
It should be no surprise that 1 entry of each took no measurable time (getTickCount() had not incremented).
At 10,001 entries, <cfloop array> and <cfloop list> took 5 and 4 milliseconds respectively, but at 11,001 (the next level up), it was 3 and 7 milliseconds respectively – neck and neck, looking in favor of <cfloop array>. <cfloop ArrayLen()> was taking 9 and 6 seconds, <cfloop collection> 21 and 17 seconds, and <cfloop StructCount()> waas taking 21 and 14. At this level we could say <cfloop array> and <cfloop list> were close, while the others were not.
At 50,001 entries, <cfloop array> and <cfloop list> are still neck and neck. They reported identical times of 11.00 milliseconds. <cfloop ArrayLen()> weighed in at 56.10ms, <cfloop collection> at 126.2ms, and <cfloop StructCount()> at 91.2ms.
By the final test of 100,001 entries, <cfloop array> and <cfloop list> had finally started to show a real difference. <cfloop array> pulled ahead as the clear winner, with at least a 10ms margin on all but one of the the 10 tests leading up to 100,001.
So what causes such a performance difference?
<cfloop ListLen()> was the clear loser by a wide margin. ListGetAt() is horribly inefficient. Each time you call it, it has to consume the string from the start, counting delimiters until it reaches position-1, then continue consuming until it reaches position. This is no surprise at all.
<cfloop collection> was the clear next-to-last-place loser. The most likely reason for this to me is that internally it needs to loop over some other type of object (in this case, most likely an array of struct keys), then needs to do a lookup within the actual structure itself (a HashMap of some form).
<cfloop StructCount()> came next. This was a bit of an non-real world scenario. We didn’t have to loop over a collection of struct keys, we knew what the struct keys were and were able to perform the loop itself in a faster fashion than looking up keys. But to output the value, we still needed to do HashMap lookups on the keys themselves.
<cfloop ArrayLen()> won the bronze. Seems to me that this is because we have to do a positional lookup to output the value for each entry. That shouldn’t be huge because internally this should be represented as a vector of pointers to the actual entries, and since each vector has a fixed memory size, we take ArrayMemoryStartPoint + position * sizeof(vector). Well, would be nice if that’s the case, but it’s not quite that simple since these arrays are dynamically sized. We actually have to do a bit of work with a table of memory references, blah blah blah. Point is we have to do a lookup (albeit cheaper than a struct lookup) to find the correct entry.
<cfloop list> took the silver. This makes sense, the iterator involved in the cfloop can remember where it left off, and each time through the loop only has to consume up to the next delimiter. It knows what the index of the previous delimiter is, and so the only lookup it has to do at all is collecting the characters from offset A to offset B (which it could actually have kept track of while it was consuming).
<cfloop array> took the gold, but not by a large margin. This also makes sense because it has the same sort of performance gain that <cfloop list> has (already knowing its current offset for the next time through the loop), and all it has to do is return a pointer to the next element in the vector. The vector iterator handles this stuff at a lower level and is able to make the best use of its own internal structures to make this as fast as possible.
Conclusion
<cfloop array> and <cfloop list> are pretty interchangeable even though the former wins the contest.
All of this being said, we are still looking at loop overhead of less than 300 milliseconds even for the slowest (other than <cfloop ListLen()>) loop type for 100,000 records. This is incredibly trivial overhead for that amount of data. So in reality which type you use probably depends more on what structures you’re already using – trying to convert to a different data container for your loop will probably cost you as many or more cycles than using the native loop type associated with wherever your data currently is.
Established Programmers Getting Started in Web Development
Posted by Eric in Programming on May 21st, 2008
An acquaintance of mine has recently graduated from college with a degree in computer science. Where he went, apparently they stressed theory over practice. He’s got some C++, Lisp, Java, and MySQL experience, but has never touched web development (neither HTML, nor even viewed source on a web page).
He’s hoping to get a job with a company that has him supporting Java applications with web front ends, so to do that he’ll need to get at least tolerable with HTML. He’s willing to go to training if there’s a course that’ll help, but the obvious concern is that he goes to a 5 day training and spends a significant amount of time covering “Web pages are viewed in web browsers” type material – that is to say, he’s concerned that intro to web development courses are going to be tailored to people looking to set up a family-newsletter or small-business-created-by-the-owner type site.
I’m recommending he start with the W3C tutorials: http://www.w3.org/2002/03/tutorials , which should get him a functional early level of knowledge. I suggested he could start out trying to make a personal site in HTML w/o leaning on a HTML editor, hopefully this gets him the rudimentary skills he needs. Other suggestions are welcome!
WebScarab-NG
Posted by Eric in Debugging, Programming on May 9th, 2008
WebScarab-NG is a really amazing tool that Brian introduced me to a few months back. It’s essentially a local proxy which you can use to capture the full details of HTTP requests traveling through it. It listens by default on port 8008 on your local address, and you can configure any software to use that port as a proxy.
If you choose, you can even configure it to intercept requests and responses, and it allow you to modify the data on the fly – really useful when you want to test fault circumstances.
How UTF-8 Encoding works
Posted by Eric in Programming on May 3rd, 2008
I spoke yesterday about Unicode, and the difference between the Unicode character set, and specific encodings of this character set. This post is a follow-up which describes in detail one particular and popular character set – UTF-8.
It’s imortant to understand that encoding is simply a means of representing a Unicode character in terms of bytes on a disk or in a network stream. In the same sense, the character λ can be encoded in HTML as one of: &lamda; , λ , or λ. These HTML entities are another form of character encoding.
To understand how UTF-8 encodings work, we have to be really certain that you have it in your head that a byte and a character are different things. Just like encoding special characters in HTML, a character in UTF-8 can be made up of one or more bytes. Such encoded characters are called muti-byte characters, because they require 16, 24, 32 (or sometimes but rarely more) bits to represent this character, corresponding of course to 2, 3, and 4 bytes.
Because each character is not made up of a fixed number of bytes, UTF-8 is called a variable-width encoding. Variable-width encodings are popular because they can reduce the storage size of the most common members of that encoding. For example, this page is encoded in UTF-8, and yet almost every character in its source code will only require a single byte.
The UTF-8 encoding is popular because especially for speakers of Latin-based languages (Europe, USA, et al.) it only requires one byte per character for our most common printed characters. Also, and unlike some other character encodigns, existing text encoded as ASCII (the old IBM PC days of 7 bits per byte – the first 128 characters in an ASCII table) translates into UTF-8 without any need for conversion. UTF-8 also supports a very large range of characters (its charater repertoir).
To understand the way UTF-8 works, we have to examine the binary representation of each byte. If the first bit (the high-order bit) is zero, then it’s a single-byte character, and we can directly map its remaining bits to the Unicode characters 0 – 127. If the first bit is a one, then this byte is a member of a multi-byte character (either the first character or some followup of it).
For a multi-byte character (any character whose Unicode number is 128 or above), we need to know how many bytes will make up this character. This is stored in the leading bits of the first byte in the character. We can identify how many total bytes will make up this character by counting the number of leading 1’s before we encounter the first 0. Thus, for the first byte in a multi-byte character, 110xxxxx represents a two-byte character, 1110xxxx represents a three-byte character, and so on.
For secondary bytes in a multi-byte UTF-8 encode character, the first two bits are reserved to indicate that this is a follow-up byte. All secondary and beyond characters are of the form 10xxxxxx. It may seem wasteful to sacrifice two bits of each follow-up byte since by the time we reach this byte, we already know that it’s part of a multi-byte character. Indeed, it is wasteful, but it is intentional, and intended to address systems which do not properly handle multi-byte character encodings. For example, this enables us to identify if a string was encoded with an alternate character encoding but is being parsed as UTF-8. It also enables us to identify strings which were incorrectly truncated.
So characters in UTF-8 can be represented in binary as:
0xxxxxxx
110xxxxx 10xxxxxx
1110xxxx 10xxxxxx 10xxxxxx
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
If you’re interested in further reading regarding Unicode and character encodings, a good place to start would be Wikipedia:
http://en.wikipedia.org/wiki/Unicode
http://en.wikipedia.org/wiki/Character_encoding
BOM – Is it part of the data?
Posted by Eric in Programming on May 3rd, 2008
This is a post in response to a comment at Ben Nadel’s blog by PaulH which I think is an interesting and important discussion, but sufficiently off-topic to the blog entry at hand that I didn’t want to completely derail the on-topic discussion.
Whereas initially BOM (Byte Order Marker U+FEFF) was intended to indicate the order of the bytes when dealing with systems which may have had little-endian or big-endian CPU’s, and so written characters in a byte order for which they are most suited while potentially interoperating with systems with opposite endianness. Their use in recent years has mostly been as a hint to byte stream -> character array string parsers as to the encoding of the string. For example, you can identify UTF-8 encoded files with a leading BOM because they will start with 0xEF 0xBB 0xBF (Unicode U+FEFF). UTF-16BE will start with 0xFE 0xFF, UTF-16LE will start with 0xFF 0xEF, and so on.
At a conceptual sense, byte order markers are not considered to be part of the data. In fact, U+FEFF is a Zero Width Non-Breaking Space, and is considered obviated within data because of its use as a BOM. You’re supposed to use U+2060 WORD JOINER instead of U+FEFF ZWNBSP. The fact that U+FEFF is a zero-width character is part of why it was chosen as BOM – if a system reads the encoding correctly but doesn’t know how to deal with BOM, it will be interpreted instead as an invisible character – exactly what we’re seeing with CFHTTP.
The problem in this case is that no character, not even zero-width characters are permitted before the processing instruction in an XML document. ColdFusion’s cfhttp function preserves the BOM as part of the data, while it’s xmlParse() function fails to handle it correctly. This is an inconsistency, and I suspect you may be able to start a holy war over which feature has the bug.
I Googled around for a while to see if I could find a source that said definitively whether a BOM is considered part of the Unicode data, or simply a hint which is intended to be dropped as part of the Unicode decoding (eg, we convert multiple bytes into single characters in the case of characters greater than U+00EF, likewise we consume the hint as a means of informing us how the file is encoded, and nothing else). This latter case has always been my understanding of it, and indeed this behavior is reinforced by many systems, including ColdFusion itself in some arenas (eg, reading a file with cffile that contains a leading BOM – the BOM will be discarded). Unfortunately other systems do seem to retain BOM, but it’s impossible to say for those systems whether this was a design decision or failure to address BOM at all as they would look the same to an outside observer.
I couldn’t find much in the way of a definitive statement for or against BOM being retained as part of the character array. The closest I could find is something you alluded to – XML 1.0 specifies that BOM is not considered to be part of the data, and should be used only to identify the endianness of the data being passed to it, and otherwise ignored. That wording is a bit ambiguous since in its original context, it’s talking about how to handle BOM at the start of a byte stream.
As to the applicability of this part of the XML standard to ColdFusion’s XML parser – ColdFusion’s XML parser isn’t dealing with a byte stream, it’s dealing with a character array. By the point we call xmlParse(), we have gotten past our need for the BOM (if we’ve already parsed the byte stream as characters, BOM can no longer affect what we do with those characters), so the XML standard on dealing with BOM no longer applies.
So this all comes down to: Is BOM part of the data or just metadata? Conceptually it’s part of the metadata, whereas the question is should it be preserved in the character array. I land firmly in the camp of it being purely metadata, and with it being desirable to discard it as part of character parsing. ColdFusion treats it as metadata in some instances and as part of the data in other instances, this inconsistency is where we see the original error.
Some software even provides an option as to whether or not BOM should be preserved as part of the data: http://www.webhostingsearch.com/blogs/richard/bom-byte-order-mark-in-biztalk-output/
In any event, CF should be consistent with how it handles BOM, and if it considers it as part of the data, then its string functions should consistently handle it as such (ie, xmlParse() should ignore it). If it considers it to be metadata, then it should always be discarded when parsing the byte stream into a character array. The fact that in some cases it discards BOM when parsing characters says to me that the design decision by Macrodobeia was to discard it when parsing characters, since someone had to have written code to this effect, but that it wasn’t applied consistently throughout.
Unicode: The absolute minimum every developer should know.
Posted by Eric in Programming on May 2nd, 2008
Over the past few years, I’ve been engaged in a few projects which have required international support. Via trial and fire, I’ve learned a fair amount about Unicode and character encoding. I now consider this to be essential knowledge for all programmers – web programmers especially. This becomes particularly important when you start dealing with strict schemas such as XML, which may care greatly what the individual characters are, and whose schema may be broken by invalidly encoding some characters.
There’s a great article here with the absurdly long yet very much accurate title of The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) by Joel Spolsky of Joel on Software fame.
It’s important to realize that Unicode is just a really big alphabet. It’s a collection of letters, glyphs, and symbols from a lot of different languages, some non-languages (eg, there’s a smiley with an eyepatch), and even some fake languages (I believe there’s some Klingon in there). It specifies nothing about what bytes you use to represent a given Unicode character, it just says that character 12345 should be such and such a symbol.
Next comes encoding. Encoding defines how we map a given Unicode character into bytes. There are many encoding schemes out there, some of them favor one language or another (ISO-8859-1, which is common in Microsoft applications favors European languages).
Not all encodings are able to represent the entire Unicode character set. The characters which can be represented by a given character set is known as that set’s character repertoir. The encoding specifies both how to represent characters in terms of bytes on a disk, and also which subset of the Unicode character set this encoding represents. The same bytes interpreted as a different character encoding will yield different glyphs.
Some encodings specify that each character is made up of some pre-determined, fixed number of bytes, while others specify that different characters are made up of different numbers of bytes – usually the most common characters are a single byte, and less common characters are multiple bytes.
One of the most common encodings is UTF-8. This is an incredibly popular character encoding, and for good reason – it’s very flexible, and uses only a single byte for the most common characters, making it also one of the most compact. I’ll talk about it some more tomorrow.
Adobe opens the file formats for SWF and FLA
Posted by Eric in Programming on May 1st, 2008
Adobe is opening up the file formats for SWF and FLA, which is major news! SWF is the format run by Flash Player, and FLA is the source format which is used to create SWF’s. With this documentation, anyone will be able to create their own FLA and SWF creation software. Previously this had been substantially reverse engineered, but there were still bits and pieces which had not been figured out.
CFThread and dividing up work
Posted by Eric in ColdFusion, Programming on April 23rd, 2008
CFThread is a wonderful addition to ColdFusion 8. It lets you perform parallel actions within your code. However, parallel programming is a complex beast under the best of circumstances.
One of the early things to realize in CF8’s threading support is that it makes a deep copy of the local variables (ala Duplicate()) when you start the thread. In this way you have a lot of thread safety, you can access and change even variables defined outside the thread space, and you really have a copy of that variable local to your thread. You don’t have to worry about other threads changing the value while you’re using it, and you don’t even have to worry about goofing it up for the parent page (the page thread).
Dividing Up the Work
A common use for threading is to divide up a lot of work so that it can be done in parallel. For example, let’s say you have a script which aggregates RSS feeds from 1,000 external sites. All that HTTP stuff is pretty quiet work, you spend a lot of time waiting for responses and the like. It’s a good candidate for parallelizing the work.
With 1,000 requests to make, it’s not a good idea to just create 1,000 threads – you’ll tie up a lot of TCP connections on your server, plus you’ll use up a lot of memory (remember, each thread is going to operate in its own memory space). So let’s decide somewhat arbitrarily that we’re only going to run 10 requests in parallel.
// How many feeds will each thread handle?
eachThreadDoesCount = ceiling(ArrayLen(feedURLs) / parallelThreads);
threadID – 1) * eachThreadDoesCount + 1>
threadID * eachThreadDoesCount, ArrayLen(feedURLs))>
Looks pretty easy, eh? There’s a critical error there though which is not obvious even by Adobe’s documentation. I’ve bolded it for you. This will end up with the earliest URLs getting fetched numerous times, and the later URLs not getting fetched at all.
The reason for this has to do in some way with how ColdFusion initiates its threads under the hood. To me, it looks like when tag is encountered, it actually spawns an initial thread to do the local variable copying. All threads which are started before this initial thread finishes the copying will get an identical set of local variables – this includes the threadID variable used in the loop. I’m not certain if that’s actually what’s going on under the hood, but the behavior is similar as if that is the case. In any event, you cannot rely on variables changed by the parent page (”page thread” by Adobe’s documentation) appearing in your cfthreads, even if that change was made before your specific thread was launched, but after the initial thread was launched.
It seems bizarre, but let me give you a piece of sample code which demonstrates it. This code is non-deterministic for me – that is to say some times I see a “correct” result, but then I immediately refresh it and get a different result.
Here you should see each worker thread having a unique loopID. Instead, for example, my code shows Worker 1 has a loopID of 1, Worker 2 = 2, Worker 3 = 3, Worker 4 = 4, but Workers 5 through 20 have a loopID of 5. If I refresh, it’s different. I’ve seen all 20 workers starting with a loopID of 1, and I’ve seen the first fiew having a loopID of 1, then the next few having a loopID of 5, then the next few having a loopID of 8, etc.
So how do you safely determine which worker you are so you know which of the set of work you should be doing? The answer, as Ray posted in a comment (and contrary to my more elaborate work-around involving locking), is to use the attributes scope:
Basically the idea is you can pass additional custom attributes to and these show up as values in a structure named “attributes” available only within the scope of your thread.
ColdFusion 8.0.1 – Nested Array/Struct Shorthand
Posted by Eric in ColdFusion, Programming on April 10th, 2008
As you probably know, ColdFusion 8 gave us a long-needed shorthand for creating arrays and structures:
Unfortunately you couldn’t nest those constructs. With the 8.0.1 updater though, you now can:
This is fantastic when you’re trying to make configurable code – a chunk of code whose basic function is tweakable by updating a few settings variables at the top instead of hard-coding them in throughout the code (for example – URLs, filesystem paths, data sources, etc).
Follow up to Real Time Command Execution Feedback Post
Posted by Brian in ColdFusion, Programming on April 9th, 2008
With ColdFuison 8.0.1 Adobe has introduced errorVariable and/or errorFile to the attributes of the tag. You can only use one of the two in the same tag.
This will give some insight once the tag has completed execution if there is an error. Before there was no way for CF to report errors to a file or to the browser.
Recent Comments