{"id":1543,"date":"2009-10-06T15:54:00","date_gmt":"2009-10-06T15:54:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vbteam\/2009\/10\/06\/hidden-costs-matt-gertz\/"},"modified":"2024-07-05T12:46:38","modified_gmt":"2024-07-05T19:46:38","slug":"hidden-costs-matt-gertz","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/vbteam\/hidden-costs-matt-gertz\/","title":{"rendered":"Hidden Costs (Matt Gertz)"},"content":{"rendered":"

(Note: there was a grievous error in this post based on a bad assumption on my art regarding VB.  Not feeling the need to hide my ignorance :-), I have instead made a number of edits in this post to bring it back to some semblance of reality.)<\/font><\/font><\/p>\n

One thing that gets me annoyed with myself is realizing that the product or service I’ve just bought has some hidden costs that I didn’t anticipate.  <\/span>It might be as complicated as realizing that my plane ticket has all sorts of byzantine surcharges and luggage costs, or as simple as making budgeting for a new killer gaming PC and forgetting about the sales tax – it seems that there are always extra costs out there that will come back to bite you.  <\/span>Being (as I have said in past postings to this blog) an inherently lazy person, and being fully caught up in our “I must have the sparkly thing right now<\/i>” culture, I’m apt to overlook the fine print in any purchase agreement unless I really force myself to slow down and pay attention to the details.  <\/span><\/font><\/font><\/p>\n

One of the times I really have to pay attention is when I’m reviewing code here at Microsoft.  <\/span>As a member of the release team that makes the final decisions as to what last-minute fixes are safe enough to be applied to an imminent release, it’s my job to take a look at the proposed fix and make sure that it doesn’t introduce more problems than it purports to solve – i.e., that it doesn’t add hidden costs.<\/font><\/p>\n

On the rare occasion that I find a problem in someone’s code, it’s usually something that’s obviously dysfunctional – a case where a variable isn’t initialized properly, or where a different team has simultaneously made a change that will render this change dangerous.  <\/span>But some of the problems are more subtle, and might not be obvious if only minimal testing and review has been done.  <\/span>Consider the following code (very similar to a case I reviewed here at work the other day):<\/font><\/p>\n

    <\/span>Public<\/span> MyList As<\/span> New<\/span> List<\/span>(Of<\/span> String<\/span>)<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>Private<\/span> Sub<\/span> Button1_Click(ByVal<\/span> sender As<\/span> System.Object<\/span>, ByVal<\/span> e As<\/span> System.EventArgs<\/span>) Handles<\/span> Button1.Click<\/p>\n

<\/span><\/p>\n

        <\/span>Dim<\/span> s As<\/span> New<\/span> System.Text.StringBuilder<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>For<\/span> i As<\/span> Integer<\/span> = 0 To<\/span> MyList.Count – 1<\/p>\n

<\/span><\/p>\n

            <\/span>s.Append(MyList(i))<\/p>\n

<\/span><\/p>\n

        <\/span>Next<\/span><\/p>\n

<\/span><\/p>\n

    <\/span>End<\/span> Sub<\/p>\n

<\/span><\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Edit<\/b>:  <\/span>This is an error in my blog post  <\/span>– I hadn’t realized that VB, unlike many other languages, only gets the value of the stop condition once (thanks to Phil Wells for pointing this out).  <\/span>To make my point, I would have to be using code like this:<\/font><\/font><\/p>\n

        <\/span>Dim<\/span> s As<\/span> New<\/span> System.Text.StringBuilder<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>Dim<\/span> i As<\/span> Integer<\/span> = 0<\/p>\n

<\/span><\/p>\n

        <\/span>Do<\/span> While<\/span> i < MyList.Count() – 1<\/p>\n

<\/span><\/p>\n

            <\/span>s.Append(MyList(i))<\/p>\n

<\/span><\/p>\n

            <\/span>i += 1<\/p>\n

<\/span><\/p>\n

        <\/span>Loop<\/span><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

The method Count() might still have a hidden cost, but in the For Loop case, I’m at least only hitting it once.  <\/span><\/span>The fact that VB only analyzes the stop condition once leads to a different issue to be aware of that I’ll cover in my next blog.<\/font><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Seems pretty simple, yes?  <\/span>When a button is clicked, the code iterates through the strings in a list and appends them to a StringBuilder, creating (for whatever reason) one long string containing all of the contents.  <\/span>And, to cursory appearances, it will function correctly. <\/font><\/p>\n

However, the code has hidden costs.  <\/span>You see, written this way, the value MyList.Count is going to be reevaluated on every iteration of the “For” loop, even though the value itself isn’t changing.  <\/span>Furthermore, my indexing into MyList, which is always with reference to the beginning of the list, will also have a non-zero impact.  <\/span>This impacts the performance of the code and will make my customers unhappy over the sloth-like operation of my application.  <\/span><\/font><\/font><\/p>\n

In this case, the cost isn’t really high, as Count() is a property wrapping something that’s stored as a private integer member, and index referencing also has tricks to speed it up, but there’s still a cost and it can add up.  <\/span>It’s even worse if the Count() call has to be calculated!  <\/span>Consider this really awful code where I’ve created my own “List” type:<\/font><\/p>\n

    <\/span>Public<\/span> Class<\/span> MyLameObject<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>‘ For some unknown reason, I’m creating my own linked list instead of using a List(Of) generic.<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>‘ Please don’t do this for real!<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>Public<\/span> data As<\/span> String<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>Public<\/span> NextMLO As<\/span> MyLameObject<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>Public<\/span> Sub<\/span> Insert(ByVal<\/span> mlo As<\/span> MyLameObject<\/span>)<\/p>\n

<\/span><\/p>\n

            <\/span>If<\/span> NextMLO IsNot<\/span> Not\nhing<\/span> Then<\/span><\/p>\n

<\/span><\/p>\n

                <\/span>NextMLO = mlo<\/p>\n

<\/span><\/p>\n

            <\/span>Else<\/span><\/p>\n

<\/span><\/p>\n

                <\/span>mlo.NextMLO = NextMLO.NextMLO<\/p>\n

<\/span><\/p>\n

                <\/span>NextMLO.NextMLO = mlo<\/p>\n

<\/span><\/p>\n

            <\/span>End If<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>End<\/span> Sub<\/p>\n

<\/span><\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

        <\/span>Public<\/span> Function<\/span> Count() As<\/span> Integer<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>Dim<\/span> ct As<\/span> Integer<\/span> = 0<\/p>\n

<\/span><\/p>\n

            <\/span>Dim<\/span> current As<\/span> MyLameObject<\/span> = Me<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>Do<\/span> While<\/span> current IsNot<\/span> Nothing<\/span><\/p>\n

<\/span><\/p>\n

                <\/span>ct += 1<\/p>\n

<\/span><\/p>\n

                <\/span>current = current.NextMLO<\/p>\n

<\/span><\/p>\n

        <\/span>    <\/span>Loop<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>Return<\/span> ct<\/p>\n

<\/span><\/p>\n

        <\/span>End<\/span> Function<\/p>\n

<\/span><\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

        <\/span>Public<\/span> Function<\/span> Item(ByVal<\/span> index As<\/span> Integer<\/span>) As<\/span> MyLameObject<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>If<\/span> index >= Count() OrElse<\/span> index < 0 Then<\/span> Return<\/span> Nothing<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>Dim<\/span> current As<\/span> MyLameObject<\/span> = Me<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>For<\/span> i As<\/span> Integer<\/span> = 0 To<\/span> index – 1<\/p>\n

<\/span><\/p>\n

                <\/span>current = current.NextMLO<\/p>\n

<\/span><\/p>\n

            <\/span>Next<\/span><\/p>\n

<\/span><\/p>\n

            <\/span>Return<\/span> current<\/p>\n

<\/span><\/p>\n

        <\/span>End<\/span> Function<\/span><\/p>\n

<\/span><\/p>\n

    <\/span>End<\/span> Class<\/span><\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>Public<\/span> MyLameObjectHeader As<\/span> New<\/span> MyLameObject<\/p>\n

<\/span><\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>Public<\/span> MyLameObjectHeader As<\/span> New<\/span> MyLameObject<\/span><\/p>\n

<\/span><\/p>\n

    <\/span>Private<\/span> Sub<\/span> Button1_Click(ByVal<\/span> sender As<\/span> System.Object<\/span>, ByVal<\/span> e As<\/span> System.EventArgs<\/span>) _<\/p>\n

<\/span><\/p>\n

Handles<\/span> Button1.Click<\/p>\n

<\/span><\/p>\n

        <\/span>Dim<\/span> s As<\/span> New<\/span> System.Text.StringBuilder<\/span><\/p>\n

<\/span><\/p>\n

        <\/span>For<\/span> i As<\/span> Integer<\/span> = 0 To<\/span> MyLameObjectHeader.Count – 1<\/p>\n

<\/span><\/p>\n

            <\/span>s.Append(MyLameObjectHeader.Item(i))<\/p>\n

<\/span><\/p>\n

        <\/span>Next<\/span><\/p>\n

<\/span><\/p>\n

    <\/span>End<\/span> Sub<\/p>\n

<\/span><\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Perhaps as a school assignment, I’ve created a singly-linked list which contains objects of type “MyLameObject” (instead of using optimized collections that we provide).  <\/span>I’ve also created a member function called “Count” which returns the number of objects in my list (starting from the current node) and another member function called “Item” which returns me a reference to a specific object in the list, as indexed from the current node.  <\/span>The code will compile and it will “work.”  <\/span>But, oh!   <\/span>It has so many<\/b> hidden costs, and if the definition of MyLameObject exists in an assembly for which I don’t have the source code, I might not even realize it!<\/font><\/p>\n

First, let’s look at button click handler.  <\/span>It’s calling Count() on every single iteration, and there will be a number of iterations equal to the value returned from Count().  <\/span>Count(), in turn, walks the entire list every time it’s called.  <\/span>So, that means that if my list contains 1000 items, that means that I’ll be referencing a MyLameObject one million times<\/i>!  <\/span>(This is what they refer to as an “O(n2<\/sup>) problem” in computer science classes.)<\/font><\/p>\n

But wait, it gets worse:  <\/span>the code for Item() calls Count() also on each iteration to verify that the index is not out of bounds – that brings us up to a count of 1001000 MyLameObject references<\/s>.  <\/span><\/font><\/font><\/p>\n

Edit<\/b>:  <\/span>As noted above, that isn’t true for VB, though it would be for many other languages<\/font><\/font><\/p>\n

And, of course, Item() itself needs to walk the list to actual get to the desired item, on every iteration – that adds 500500 more object hits (using the n(n\n+1)\/2 formula) , for a grand total of 1501500<\/s> 1500500 object hits. And all that just to concatenate 1000 strings!  <\/span>That, I fear, is going to slow down my code’s performance somewhat.<\/font><\/p>\n

Now, of course I could add code to get track of values for Count(), and that would reduce my cost to a third of what it was.  <\/span>I could use some clever hashing algorithm to more easily get to the items while still being able to use method calls.  <\/span>I could enumerate the list myself instead of relying on “Count” or on “Item,” and that would really cut my costs down dramatically.  <\/span>Or, best of all, I could avoid reinventing the wheel and using the classes that VB.NET already supplies for me, since we do our best to optimize them.  <\/span><\/font><\/font><\/p>\n

But that’s not the point that I’m trying to make here.<\/span><\/font><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

(Note: there was a grievous error in this post based on a bad assumption on my art regarding VB.  Not feeling the need to hide my ignorance :-), I have instead made a number of edits in this post to bring it back to some semblance of reality.) One thing that gets me annoyed with […]<\/p>\n","protected":false},"author":258,"featured_media":8818,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[21,22,195],"tags":[101,165,166,167],"class_list":["post-1543","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-im-a-vb","category-matt-gertz","category-visual-basic","tag-matt-gertz","tag-vb2005","tag-vb2008","tag-vb2010"],"acf":[],"blog_post_summary":"

(Note: there was a grievous error in this post based on a bad assumption on my art regarding VB.  Not feeling the need to hide my ignorance :-), I have instead made a number of edits in this post to bring it back to some semblance of reality.) One thing that gets me annoyed with […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/posts\/1543","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/users\/258"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/comments?post=1543"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/posts\/1543\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/media\/8818"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/media?parent=1543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/categories?post=1543"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/vbteam\/wp-json\/wp\/v2\/tags?post=1543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}