List vs ArrayList, Dictionary vs Hashtable

OK let me go through these one by one ...

>Anyway, being a C++ programmer since the age of 11 (and a BASIC programmer since the age of 8), *please* allow me to tell you that:
>gregoryyoung: I ***know*** what I'm saying, and I've given the ***exact*** answer to the question!!!

Well let's take a good look at that answer ...l


> None of these types are thread safe by default as is being implied
>I beg you pardon?!!!!!!!!!!!!!
>Microsoft says: Hashtable is thread safe for use by multiple reader threads and a single writing thread.

All types are safe for multiple readers ... multiple readers with no writers does not need locking this is MT 101 .. any object which is being treated as being immutable (readonly) is inherently threadsafe. There is no locking done in either version of the types unless you do it yourself or use the .Synchronized versions. Microsoft in this statement is saying that the writes to the ArrayList/List are atomic for a single writer and can therefore be done without external locking while maintaining thread safety ... this is not done through locking but through order of operations for dealing with the internal array growths ... interestingly enough this gaurentee does not always apply .. if you are using a List<valuetype> where the size of a value type is larger than the size of a reference in the runtime (32 bits for most people 64 bits in some archtiectures) the writing of data is no longer atomic (the CLR assures that writes of reference size or smaller are atomic). Because of this even 1 writer/many readers is not thread safe for value types that are say 128 bits as a reader may get a partial read ... The reason for the diffrence is that since the ArrayList boxes everything it *always* deals with reference size ites internally which are assured logically to be <= the size of a reference and therefore atomic ... but again don't take *my* word for it reflector is your friend I can assure you that there is not locking in it, check for yourself.


> For reference types the type conversions still carry runtime overhead

>I beg you pardon?!!!!!!!!!!!!!
>Please take a look at the output of the application listed below!

Yes note that there is STILL a 1 second difference ... the performance difference will be small but it exists you are talking about the difference of a test/branch being generated to handle the cast. The runtime overhead assocated with the cast can easily be seen by looking at the unmanaged code in question that gets generated by the JIT, as a C++ developer since you were 11 I figured you would have botherred to look at this.

The funny part is that your example has useless code in it .. in particular adding the cast for the generic version which is optimized out anyways which is exactly the point I was saying ...

foo = (IfIWereYouIWouldNotHaveSaidThatThereIsNoTruthToBeFoundInTheAboveStatementWhenIAmTalkingToNayerNaguib) a[i]; //set to dummy variable to keep it from being optimized out

should be

foo = a[i]; //set to dummy variable to keep it from being optimized out


>Usually the runtime environment has no idea about type safety (or in other words generic types)!!! Only the compiler will watch out for mistakes, which >***definitely*** means that using generic types will ***never*** have a performance impact, unless, of course in such a ***very*** special case, the >compiler replaces the primitive objects with their corresponding wrappers!!!

As for value types being a very specific case I would disagree... but fair enough I also discussed reference types though .. as to whether my example should of been of a reference type, I will buy that... It would have been a more fair comparison but ...

You really have no clue about the runtime .. The runtime certainly does have an idea about type safety .. The case I am referring to is a narrowing conversion which the runtime has to check ... This is the same as in the ArrayList case (arraylist stores as object and you must use a narrowing conversion from object when you retrieve data).

        static void Main(string[] args) {
            int foo = 5;
            object obj = foo; //widen to object
            string s1 = (string)obj;
            Console.Write(s1);
        }


This code is perfectly valid as far as the compiler is concerned yet the runtime discovers it is not a valid conversion .. how? by generating code to check after the conversion ... Here is checking it using SOS ..

.load SOS
extension C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\SOS.dll loaded
!Name2EE ConsoleApplication35.exe ConsoleApplication35.Program.Main
PDB symbol for mscorwks.dll not loaded
Module: 00912c14 (ConsoleApplication35.exe)
Token: 0x06000001
MethodDesc: 00912fd8
Name: ConsoleApplication35.Program.Main(System.String[])
JITTED Code Address: 00df0070

!u 00df0070
Normal JIT generated code
ConsoleApplication35.Program.Main(System.String[])
Begin 00df0070, size 57
>>> 00DF0070 56               push        esi
00DF0071 B91CED0F79       mov         ecx,790FED1Ch
00DF0076 E8A11FB1FF       call        0090201C (JitHelp: CORINFO_HELP_NEWSFAST)
00DF007B 8BD0             mov         edx,eax
00DF007D C7420405000000   mov         dword ptr [edx+4],5
00DF0084 8BF2             mov         esi,edx
00DF0086 85F6             test        esi,esi
00DF0088 7418             je          00DF00A2
00DF008A 813EE0A30F79     cmp         dword ptr [esi],790FA3E0h
00DF0090 7502             jne         00DF0094
00DF0092 EB0E             jmp         00DF00A2
00DF0094 8BD6             mov         edx,esi
00DF0096 B9E0A30F79       mov         ecx,790FA3E0h
00DF009B E80CBB0F79       call        79EEBBAC (JitHelp: CORINFO_HELP_CHKCASTCLASS_SPECIAL)
00DF00A0 8BF0             mov         esi,eax
00DF00A2 833D84102B0200   cmp         dword ptr ds:[022B1084h],0
00DF00A9 750A             jne         00DF00B5
00DF00AB B901000000       mov         ecx,1
00DF00B0 E857D75578       call        7934D80C (System.Console.InitializeStdOutError(Boolean), mdToken: 0600070f)
00DF00B5 8B0D84102B02     mov         ecx,dword ptr ds:[022B1084h]
00DF00BB 8BD6             mov         edx,esi
00DF00BD 8B01             mov         eax,dword ptr [ecx]
00DF00BF FF9090000000     call        dword ptr [eax+00000090h]
00DF00C5 5E               pop         esi
00DF00C6 C3               ret


Oh what is that call? 79EEBBAC (JitHelp: CORINFO_HELP_CHKCASTCLASS_SPECIAL) do you think this maybe just maybe is checking that the narrowing cast is ok? Did you notice that call was not generated for widenning conversions? If you remember I said for reference types this is why generics will be slightly faster given they are using the same algorithm in fact we could take your example and make it do more reading to show this even further ... In the original example most of the overhead was in creating the new objects (lists/arraylists in the BCL are O(1) on inserts and lookups) so lets try getting that lookup to be used more

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication34 {
    using System.Collections;
    using System;
    using System.Collections.Generic;

    class Program {
        static Foo foo;
        static int iterations = 100000;
        public static void TestArrayList() {
            ArrayList a = new ArrayList();
            for (int i = 0; i < iterations; i++) {
                Foo x =
                     new Foo();
                x.x = i;
                x.y = i;
                a.Add(x);
            }
            for (int j = 0; j < iterations; j++) {
                for (int i = 0; i < iterations; i++) {
                    foo = (Foo)a[i]; //set to dummy variable to keep it from being optimized out
                }
            }
        }

        public static void TestGenericList() {
            List<Foo> a =
                 new List<Foo>();
            for (int i = 0; i < iterations; i++) {
                Foo x =
                     new Foo();
                x.x = i;
                x.y = i;
                a.Add(x);
            }
            for (int j = 0; j < iterations; j++) {
                for (int i = 0; i < iterations; i++) {
                    foo = a[i]; //set to dummy variable to keep it from being optimized out
                }
            }
        }
        static void Main(string[] args) {



            System.Diagnostics.Stopwatch s = new System.Diagnostics.Stopwatch();
            s.Start();
            TestArrayList();
            s.Stop();
            Console.WriteLine("ArrayList = " + s.Elapsed);
            s.Reset();
            s.Start();
            TestGenericList();
            s.Stop();
            Console.WriteLine("List<Foo> = " + s.Elapsed);
        }
    }

    class Foo {
        public int x;
        public int y;
    }
   
}

output:

ArrayList = 00:02:02.9766305
List<Foo> = 00:00:49.3661096
Press any key to continue . . .

Funny how that works eh the generic version is now twice as fast .. perhaps there is something to be said about that runtime check? Just to be complete though here are the reading loops from the two methods.

TestArrayList ...
00DF01F6 833DD02F910000   cmp         dword ptr ds:[00912FD0h],0
00DF01FD 7E53             jle         00DF0252
00DF01FF 33FF             xor         edi,edi
00DF0201 833DD02F910000   cmp         dword ptr ds:[00912FD0h],0
00DF0208 7E3D             jle         00DF0247
00DF020A 8BD7             mov         edx,edi
00DF020C 8BCB             mov         ecx,ebx
00DF020E 8B01             mov         eax,dword ptr [ecx]
00DF0210 FF5054           call        dword ptr [eax+54h]
00DF0213 8BF0             mov         esi,eax
00DF0215 85F6             test        esi,esi
00DF0217 7418             je          00DF0231
00DF0219 813E103C9100     cmp         dword ptr [esi],913C10h
00DF021F 7502             jne         00DF0223
00DF0221 EB0E             jmp         00DF0231
00DF0223 8BD6             mov         edx,esi
00DF0225 B9103C9100       mov         ecx,913C10h
00DF022A E87DB90F79       call        79EEBBAC (JitHelp: CORINFO_HELP_CHKCASTCLASS_SPECIAL)
00DF022F 8BF0             mov         esi,eax
00DF0231 8D15C41E2B02     lea         edx,ds:[022B1EC4h]
00DF0237 E8EA370879       call        79E73A26
00DF023C 83C701           add         edi,1
00DF023F 3B3DD02F9100     cmp         edi,dword ptr ds:[00912FD0h]
00DF0245 7CC3             jl          00DF020A
00DF0247 83C501           add         ebp,1
00DF024A 3B2DD02F9100     cmp         ebp,dword ptr ds:[00912FD0h]
00DF0250 7CAD             jl          00DF01FF

TestGenericList...


As you can see the big difference is ... tada the call to JitHelp: CORINFO_HELP_CHKCASTCLASS_SPECIAL and the inlining is a bit different ..

00DF02B7 833DD02F910000   cmp         dword ptr ds:[00912FD0h],0
00DF02BE 7E42             jle         00DF0302
00DF02C0 33FF             xor         edi,edi
00DF02C2 833DD02F910000   cmp         dword ptr ds:[00912FD0h],0
00DF02C9 7E2C             jle         00DF02F7
00DF02CB 3B7E0C           cmp         edi,dword ptr [esi+0Ch]
00DF02CE 7205             jb          00DF02D5
00DF02D0 E83F395B78       call        793A3C14 (System.ThrowHelper.ThrowArgumentOutOfRangeException(), mdToken: 060000d8)
00DF02D5 8B4604           mov         eax,dword ptr [esi+4]
00DF02D8 3B7804           cmp         edi,dword ptr [eax+4]
00DF02DB 7329             jae         00DF0306
00DF02DD 8B44B80C         mov         eax,dword ptr [eax+edi*4+0Ch]
00DF02E1 8D15C41E2B02     lea         edx,ds:[022B1EC4h]
00DF02E7 E844360879       call        79E73930
00DF02EC 83C701           add         edi,1
00DF02EF 3B3DD02F9100     cmp         edi,dword ptr ds:[00912FD0h]
00DF02F5 7CD4             jl          00DF02CB
00DF02F7 83C301           add         ebx,1
00DF02FA 3B1DD02F9100     cmp         ebx,dword ptr ds:[00912FD0h]
00DF0300 7CBE             jl          00DF02C0

BTW: If you are wonderring what CORINFO_HELP_CHKCASTCLASS_SPECIAL there is the source for it from the ROTOR distribution...

oh and ...

>>Congratulations for the points though! Oh, and by the way, I'd go "understand understand understand" rather than "measure measure measure"!

I did understand; I explained WHY the generic type was faster which you failed to do. In fact your post had two incorrect statements it being both offer no different thread safety gaurentee (except for as described with generics being slightly different due to not boxing) and it IS the runtime type checking which is causing the difference ... It seems to me to be a fair statement on my part that there was no truth in your post.

Next time you decide to write a post like this it would probably be best to have your facts straight.

>When performing a test using 100,000,000 read/write operations, I guess a performance difference of 1 second is not what the author of the question was ?>interested to know! Also, showing that the generic type needs about 10% of the time to finish (when the actual value is around 95%) is **certainly a joke** >rather than an unfair comparison.

Perhaps this is because the lookup (which is where the performance cost is found) is only using up <>  10% of your original TOTAL test time? (The time is mainly spent creating and inserting new objects) .. The fact that it is twice as slow or more on reads I feel is quite important since they are roughly equivalent on adds.

>Did I not use the word "usually"?? Well, although .NET seems to be an exception, I repeat that *usually* the runtime knows nothing about type safety. You >should realize this when you think about the case in which you will use generic code with old "pre-generic" code, in which case the runtime will need to >explicitly check for casts, unless in .NET you are not allowed to do that. Anyway, this is too much detail to know about a runtime environment when you >know about 25 programming languages.

Last I checked this is a .NET TA ... So in other words you are saying your post is actually wrong? That is 1/2 of your post you admitted to be wrong yet attack me for saying its wrong? We will look at the other 1/2 in a minute.

For the rest of your statement ... I don't think anyone cares about how *insert your other runtime* does things ... odd though that java does things the same way ... in fact logically you have no choice but to enforce runtime type safety if you want type safety at all .. a narrowing conversion cannot be caught by the compiler and must be checked at runtime .. perhaps you would like to provide an example of a runtime which does not do this?

Consider the following code in your favorite runtime .. How will your compiler pick this up?

public interface IFoo {
   void Bar(object);
}

public class Imp : IFoo{
   public void Bar(object o) {
       string s = (string) o;
   }
}

IFoo f = GetIFoo();
int i = 4;
f.Bar(i);

Since you are calling indirectly through an interface the compiler cannot always know which object that meets IFoo it will go to ... Because of this it can't statically check the type it needs to pass ... When the narrowing call happens you *have* to check it at runtime in order to figure out that there is a problem.

In general if I were you I might consider no longer offerring "expert" advice in the .NET CLR which you admit that you don't know or care about the details of.

>Execuse me, Hastable *does* guarantee thread safety for multiple readers/single writer as I have stated above (without calling the Synchronized method), >which is *really* where you should discuss performance issues. Also, when talking about runtime type checking, I used the word "usually", which is again >correct! The fact that you tried to show a 1000% difference in performance was such a joke, that the 1 second difference when performing 100,000,000 >read/write operations (18 sec.) is certainly not a problem to the author!

Hashtable does yes  .. the REASON (as you apparently did not manage to figure this out in the last post (the relationship is the same as that of ArrayList and List<T>) that it supports this guarentee is the boxing (it will only ever deal with reference types .. a reference type insures an action on an object the size of or smaller than the size of a reference and will therefore be atomic for the single writer (and visible consistently to the readers since the code that physically sets the memory is atomic).. it is the same exact thing I described for ArrayList vs List<T>  the SAME reasons apply to HashTable and Dictionary<T> ... The generic version will also not have the guarentee for value objects larger than 32 bits ... THE ONLY DIFFERENCE IS IN THE SIZE OF THE DATA BEING HANDLED INTERNALLY AS A COPY OF DATA SIZE OF REFERENCE OR SMALLER IS ATOMIC. The is no threading code in either class and there is *no* performance difference due to this unless you are dealing with boxed vs unboxed types in generics in which case it would still be the same by forcing the generics to box as well... The generic vs non-generic versions in fact offer the same threading contract for *ALL* reference types and only differ for value types which in your own words are a "***very*** special case".

So I have now finished showing your second statement to be non-factual ... I believe this is your entire post?

I also showed a 2x performance difference using reference types when one actually focuses on the read operations which is where the difference is (or did you miss that) ... the question was simply are generics faster and the answer is yes ... simply because you loaded extra weight onto the adds which are nearly identical for reference types ignoring my statement about the slowness being on the read side does not make your numbers valid (your code was spending about 90% of its time doing writes 90% of 18 seconds <> 16.2 seconds ... so you are actually looking at more than double speed for generics on the read side (which I showed as well). I also was very clear on specifying that the difference is greater in value types (as there is no boxing) but exists for reference types as well (for another reason). Again try *only* doing the reads since this is where the difference lies and reads are usually 100-1000ss of times or greater in count to writes on a hashtable in a real world scenario.

Again your two initial points were...

1) It is thread safety differences that cause performance differences
2) Type checking has no runtime overhead

Both are incorrect. You can continue trying to move the dicussion off into other areas like "what other runtimes do" but that is of little consequence to me. I stand by my statement that your original post was incorrect on both counts and therefore worthless ...


p.s.
"and it seems that you are only trying to prove knowledgeable and correct"

You mean by putting up pesky things like facts and proofs of those facts? Yeah I am guilty of this but atleast I am not trying to post a resume as my proof ;)