Mutability, Linked Lists, and Enumerators (C# vs. Objective-C 2.0)

by Jon Davis 30. August 2008 22:22

A few job interviews ago, I was asked about the meaning and/or significance of the term "immutable". I knew that immutable means doesn't and cannot change, and that value types (numbers and strings) and structs in C# are immutable. I knew that structs being value types get stored on the stack, and, if small, tend to be more performant. But I didn't have the background to put two and two together, so I wasn't able to explain why it mattered.

I'm still trying to wrap my hands around how stack optimizations really work, actually. But meanwhile, another job interview asked me what I knew about data structures and, "if .NET had no arrays, how would you manage multiple objects"? I was shocked with myself. These were rediculously simple questions, going back to the basics of computer science. But, for that matter, these were among those rare questions that favor the value of college education, which I lack, over experience. But it takes neither college education nor much experience to suggest a "delimited list in a string" which I didn't even think about for some weird reason--although, technically, any such serialization requires an array of char or byte.

I could be wrong but I *think* the correct answer to "in the absence of .NET arrays, how could you manage a set of n objects" would be to create a linked list. Having been abstracted from how lists work for so long, I never even looked this simple thing up until now.

http://en.wikipedia.org/wiki/Linked_list

http://en.wikipedia.org/wiki/Stack_(data_structure)

Glad that's over. I feel so dumb (and no, darn it, I did NOT ride the short bus to school!!), but refreshing myself on that is finally behind me.

Anyway, back to the mutable vs. immutable discussion, the Cocoa API in the Mac OS X world makes a strong emphasis on isolating certain objects, most notably collection objects (NSSet, NSArray, NSDictionary) as either mutable (NSMutableSet, NSMutableArray, NSMutableDictionary) or immutable. They're completely different classes, that perform the same function but with different optimizations, so the immutable (unchanging) version, which is the default (lacking the "Mutable" in the name), is extremely performant.

C#'s APIs and compiler abstract this stuff so significantly that most C# developers (like me) would likely find all this really odd.

Here's the blog post that motivated me to post this. http://cocoadevcentral.com/articles/000065.php 

Incidentally, I noticed something else about Cocoa. In C#, the syntactically-ideal iteration loop for a collection looks like this:

foreach (string s in myArray) {
    Console.WriteLine(s);
}

The problem is that foreach typically has a performance hit versus using

for (int i=0; i<myArray.Length; i++) {
    string s = myArray[i];
    Console.WriteLine(s);
}

.. which happens to be fuglier. And, to be honest, it shouldn't be faster when working with lists because an indexer has to iterate through the list from the top to find the i node, whereas an enumerator on a linked list should require no reiteration. So I don't get it.

Meanwhile, though, C# 2.0 introduced List<string>, which offers the delegate-driven ForEach( delegate ( string s) { .. } );, which is far more performant.

C# 2.0:
myList.ForEach ( delegate (string s) {
    Console.WriteLine(s);
} );

C# 3.0:
myList.ForEach( s => Console.WriteLine(s); );

In C#, AFAIK, foreach internally just instantiates an IEnumerable object's IEnumerator object and then calls its MoveNext() method, but then so does List<T>.ForEach, so I don't know (haven't looked at the MSIL or Reflector) what it's doing different between the two.

But Objective-C 2.0 apparently went through a wholly different process of evolution, where its foreach equivalent is actually much faster than its enumerator MoveNext() equivalent.

http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC/Articles/chapter_8_section_1.html
http://cocoawithlove.com/2008/05/fast-enumeration-clarifications.html

Interesting stuff.

http://theocacao.com/document.page/510

Comments

Add comment


(Will show your Gravatar icon)  

  Country flag

biuquote
  • Comment
  • Preview
Loading




 

Powered by BlogEngine.NET 1.4.5.0
Theme by Mads Kristensen

About the author

Jon Davis (aka "stimpy77") has been a programmer, developer, and consultant for web and Windows software solutions professionally since 1997, with experience ranging from OS and hardware support to DHTML programming to IIS/ASP web apps to Java network programming to Visual Basic applications to C# desktop apps.
 
Software in all forms is also his sole hobby, whether playing PC games or tinkering with programming them. "I was playing Defender on the Commodore 64," he reminisces, "when I decided at the age of 12 or so that I want to be a computer programmer when I grow up."

Jon was previously employed as a senior .NET developer at a very well-known Internet services company whom you're more likely than not to have directly done business with. However, this blog and all of jondavis.net have no affiliation with, and are not representative of, his former employer in any way.

Contact Me 


Tag cloud

Calendar

<<  August 2020  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

View posts in large calendar

RecentPosts