|
Hi,
I am inclined to doubt your measurements a bit; they seem to indicate an elapsed time of
a few tens of milliseconds, which is quite possible to measure in the wrong way (see e.g.
my timers article).
I would suggest you time a ten times bigger job, and then repeat it say 5 times and watch
the numbers. Also make sure the start conditions are the same, i.e. array loaded or not loaded
in memory before starting the timing, code JIT-compiled, etc.
I trust Array.IndexOf() to be in the same league as a simple C implementation.
|
|
|
|
|
Luc Pattyn wrote: I would suggest you time a ten times bigger job, and then repeat it say 5 times and watch
the numbers.
I expanded the repetition count a hundredfold. I had been running the tests repeatedly before; I wouldn't expect any JIT code to be purged between reps. The difference is no longer quite as great, but it's still pretty significant. Repeating 100,000 times the same search of 10,000 elements takes about 4.5 seconds with IndexOf, versus 3 seconds for the DLL.
Probably better to use a different algorithm than worry about search time, since even a 33% performance improvement probably won't be enough (though if I could get a 33% improvement just by changing an 'IndexOf' to something else, I wouldn't turn it down). I wish I knew of better ways to search for things so I could avoid reinventing the wheel.
My intention was to create a replacement for Dictionary which would add methods to purge items during an enumeration, and to perform a shallow clone. The implementation holds an array of hash values; it works well for small dictionaries, but gets a little boggy as things get larger. The majority of data sets will probably be ten items or less, but some may reach as high as 10,000. It seems that even the simple integer search becomes problematical for the larger data sets.
The dictionary is actually intended as part of a hierarchical collection class which needs to support intersection, difference, and union operations. I don't know if you're aware of any such thing already existing. My present implementation isn't horrible, but it gets a little bogged down sometimes. Something faster would be nice.
|
|
|
|
|
I don't know whether they will help with your particular problem but two collection libraries that you could investigate are PowerCollections[^] and C5[^]. The former is easier to use and better documented but the latter is more powerful. I've only used the former in anger and only sparingly. PowerCollections is less signifiacnt in the .NET 3.5 world though.
Kevin
|
|
|
|
|
Kevin McFarlane wrote: I don't know whether they will help with your particular problem but two collection libraries that you could investigate are PowerCollections[^] and C5[^].
I'll take a look at those. Right now I'm coding in VB.net; it seems from a quick glance that those libraries are in C#. How would one integrate the C# libraries into a VB.net executable using either VS2005 or VBexpress2005?
BTW, on a related note: right now I'm using both VBexpress2005 and VS2005 so that I can have different editor colors and taskbar icons for my VS projects from my VBE projects; this makes it easier to make sure I don't go editing files in the wrong project. Is there any way to set things like taskbar icon or editor colors on a per-project basis? I'm thinking I might be better off just using VS2005 for everything.
PS--I find it curious that the VisualBasic.Collection is in many ways superior to the other collection types. Its performance seems to be generally comparable to Dictionary, but it allows access by index and deletion during enumeration. Though it lacks some features that would be essential for emulating a Dictionary (e.g. enumeration of key-value pairs) and it has some other annoying weirdnesses (e.g. indices starting at 1 rather than zero, reversed arguments on the .Add method, etc.) it seems like the underlying data structure is pretty good. I wonder why Microsoft never implemented any class which shared the features, but not the limitations?
|
|
|
|
|
supercat9 wrote: it seems from a quick glance that those libraries are in C#. How would one integrate the C# libraries into a VB.net executable
Just add a reference to the DLL in the usual way.
Kevin
|
|
|
|
|
Hi,
1.
Array.IndexOf() returns the first match, which makes it essentially a linear search.
What you want is a "find any" that scales well, let's say a hash table.
As you know, when searching becomes expensive, you must invest in sorting, and the best way
for sorting often is "sort while growing" i.e. keep the list sorted at all times.
2.
.NET has a SortedList class, which is actually a Dictionary. It keeps its keys in sorted order
at all times.
3.
Wouldn't it be better to inherit from Dictionary and add the functionality you want?
I guess you can replace the Add and Remove methods, so you are aware of those operations,
then create your own IEnumerable implementation which could use indices and "return yield".
4.
It may be unwise to come up with an IEnumerable that behaves quite differently from regular
IEnumerables, those that do fail when the collection gets modified at all.
5.
You might use Reflector (or look into the Rotor source) to see how they went about it
in the first place.
|
|
|
|
|
Mark Salsbery
Microsoft MVP - Visual C++
![Java | [Coffee]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/coffee.gif)
|
|
|
|
|
Luc Pattyn wrote: 1. Array.IndexOf() returns the first match, which makes it essentially a linear search.
What you want is a "find any" that scales well, let's say a hash table.
There are a number of approaches that can be used. I figured I would try the IndexOf approach to see how far it would scale before the linear term became too dominant. The answer is, not quite far enough.
As noted, the most common number of items is probably below ten. Presently I start with a 16-element array and double the number of elements every time it overflows. If I start with a hash table, then the small dictionaries are going to be stored very inefficiently. Perhaps the thing to do would be to start with an array, and switch to a 16-way hash table when the number of elements exceeds 256, a 256-way hash table if the number of elements exceeds 4096, and a 4096-way hash table if it exceeds 65,536. Regenerating the hash tables at each boundary case wouldn't be free, but such the vast majority of elements would be regenerated at most once.
Luc Pattyn wrote: 3.
3. Wouldn't it be better to inherit from Dictionary and add the functionality you want? I guess you can replace the Add and Remove methods, so you are aware of those operations, then create your own IEnumerable implementation which could use indices and "return yield".
The Dictionary class does not expose its inner workings. While it would be possible to implement something like the 'DeleteForAll' method that's available on a List, such a method would have to queue up a list of keys and then process deletion using the list. This would require a key lookup for every entry to be deleted, whereas a well-constructed DeleteForAll primitive shouldn't require any key lookups.
Luc Pattyn wrote: 4. It may be unwise to come up with an IEnumerable that behaves quite differently from regular
IEnumerables, those that do fail when the collection gets modified at all.
So you're saying that working sensibly when a collection is changed during enumeration would be a breaking change?
Luc Pattyn wrote: 5. You might use Reflector (or look into the Rotor source) to see how they went about it
in the first place.
I'm not familiar with those things.
BTW, after posting my earlier message, I was thinking that for my hierarchical collection it might be better to build in whatever sort of dictionary implementation I'm using rather than using a dictionary-style object, since copy-on-write cloning would probably work wonders for performance and I don't think such a paradigm is apt to be useful with anything resembling a standard Dictionary (a Dictionary could implement copy-on-write shallow cloning, but in my scenario what's needed is copy-on-write deep cloning; that would require that when an object held in the dictionary is modified, it notify the dictionary so that the dictionary can perform the necessary hard cloning operation).
|
|
|
|
|
supercat9 wrote: working sensibly when a collection is changed during enumeration would be a breaking change?
yep, your SpecialDictionary.GetEnumerator() would behave quite different from
List.GetEnumerator() and others. I'm not saying better or worse, just different.
Which would tend to be confusing to readers/users of your code.
supercat9 wrote: I'm not familiar with those things.
The ultimate dictionary[^] will tell you more on Reflector, a very useful programming tool that generates pseudo-source-code for existing .NET assemblies.
|
|
|
|
|
Luc Pattyn wrote:
yep, your SpecialDictionary.GetEnumerator() would behave quite different from
List.GetEnumerator() and others.
What sort of code would rely upon having a collection throw an exception on the next iteration of an enumerator following a change? To my mind, it would be reasonable to require an exception if the enumerator is incapable of functioning without malfunction, but if the enumerator can function without malfunction, why shouldn't it?
Actually, I find the design of the collection classes to be a pretty incredible mish-mosh. The Collection type doesn't mind deletion during enumeration; in a lot of ways it's a nice class, but it doesn't provide generic support, it isn't compatible with anything else, and seems to be deprecated despite its reasonable performance and unique abilities. As for other classes, HashTable offers better performance than Dictionary, but it's not compatible. It's useful that an iDictionary can return the Keys and Values properties, but they require absurdly broad interfaces. Having an iDictionary.Values support iEnumerable (which returns values rather than key-value pairs) is useful. But having it support an Add method? What is a Dictionary supposed to do if one attempts someDictionary.Values.Add(whatever)? The semantics seem totally nonsensical to me.
Incidentally, I also find it unfortunate that Microsoft didn't provide a WeakDelegate type. Adding some events to collections would make them more powerful, but unfortunately it would also create substantial risks of memory leakage.
|
|
|
|
|
Hi,
1.
Code using GetEnumerator might go without locks and trust an Exception is thrown when the collection gets changed somehow (e.g. by another thread, possibly by someone else's code). So there is some ease of use in such a case (as there is for the author of the collection's enumerator itself).
2.
The collection classes are not perfect indeed. This is partly due to the fact that some of them got invented before C# offered generics. Several 1.x methods/properties return arrays and special kinds of lists (e.g. TabControl.TabPages) where a simple List< T> would do, and would be easier to handle. Also I am not fond about the choosen names (as in SortedList which is a Dictionary, not a List).
3.
You are right about the weak delegate stuff. I trust you've read this article[^] on the subject?
|
|
|
|
|
Luc Pattyn wrote: 1. Code using GetEnumerator might go without locks and trust an Exception is thrown when the collection gets changed somehow (e.g. by another thread, possibly by someone else's code). So there is some ease of use in such a case (as there is for the author of the collection's enumerator itself).
Do any of Microsoft's collection objects guarantee that they will throw exceptions if they are being read by one thread while another thread modifies them? While I expect that would often occur, it's dangerous to make unfounded assumptions regarding thread safety.
2. The collection classes are not perfect indeed. This is partly due to the fact that some of them got invented before C# offered generics. Several 1.x methods/properties return arrays and special kinds of lists (e.g. TabControl.TabPages) where a simple List< T> would do, and would be easier to handle. Also I am not fond about the choosen names (as in SortedList which is a Dictionary, not a List).
I wonder why there isn't a more modern version of the VisualBasic.Collection class which includes all its features?
3. You are right about the weak delegate stuff. I trust you've read this article on the subject?
I have. I'm not sure I totally trust the concept of dynamically-generated code, but the performance seems good. I also came up with my own variation which unfortunately doesn't work with standard event-based code but has a few benefits of its own. I haven't benchmarked it, though.
An event subscriber must support interface iDelegLink(of T) for some type T; to send an event, a publisher invokes sendEvent(of T)(data as T) which ends up calling Execute(sender as Object, tag as Object, data as T) as Boolean; invocation is done by performing a TryCast on a WeakReference to turn it into an iDelegLink(of T) whose Execute method is then called. If the Execute function returns true, the subscription will be canceled; otherwise it will remain.
Unlike the normal event system using delegates, mine performs thread-safe lock-free event subscription and unsubscription in constant time (an event subscriber must either keep a subscription object returned when it subscribed to the event, or it must remain subscribed until the next time the event is called, whereupon it can unsubscribe by returning True.)
|
|
|
|
|
Hi,
supercat9 wrote: Do any of Microsoft's collection objects guarantee that they will throw exceptions if ...
No, there is no thread safety in general. However GetEnumerator returns an IEnumerable and that promises an InvalidOperationException when the collection gets modified (see Current and MoveNext). I trust that works fine even when two threads are involved; it would be my guess they have some kind of generation number or so that gets compared on every invocation of Current/MoveNext.
supercat9 wrote: I wonder why there isn't a more modern version of the VisualBasic.Collection class which includes all its features?
I don't know. In fact I was unaware of Collection class until you mentioned it earlier. There are several classes marked "Visual Basic" and I would guess they mainly exist for compatibility or easier upgradability reasons where old VB code is involved??
supercat9 wrote: mine performs thread-safe lock-free event subscription and unsubscription in constant time
Sounds like a good subject for a nice article. Any plans?
|
|
|
|
|
Luc Pattyn wrote: No, there is no thread safety in general. However GetEnumerator returns an IEnumerable and that promises an InvalidOperationException when the collection gets modified (see Current and MoveNext). I trust that works fine even when two threads are involved; it would be my guess they have some kind of generation number or so that gets compared on every invocation of Current/MoveNext.
The Collection object returns an iEnumerator that does not throw an exception if the underlying collection is modified.
Luc Pattyn wrote: I don't know. In fact I was unaware of Collection class until you mentioned it earlier. There are several classes marked "Visual Basic" and I would guess they mainly exist for compatibility or easier upgradability reasons where old VB code is involved??
The VB 'collection' object allows modification during enumeration, which is a useful feature. Why can't Microsoft offer any non "visualbasic" key-value-pair object which does likewise? Any code which relies upon an iEnumerable to throw an exception if the underlying structure is modified will fail when passed the enumerator from a VisualBasic.Collection.
Luc Pattyn wrote:
Sounds like a good subject for a nice article. Any plans?
Dunno. I'm hardly a VB expert. I don't know whether people would consider it worthwhile or stupid.
modified on Sunday, November 9, 2008 9:39 PM
|
|
|
|
|
Twice as slow as a well-optimised C version is a little surprising, but not overly. The performance of the JIT certainly isn't on-par with the better compilers yet.
Searching for an integer in a large array is more a sign of bad data structure design. 40us vs 20us is fairly irrelevant when its fairly obvious you have some O(n) complexity that you want removed.
|
|
|
|
|
Mark Churchill wrote: Searching for an integer in a large array is more a sign of bad data structure design. 40us vs 20us is fairly irrelevant when its fairly obvious you have some O(n) complexity that you want removed.
O(n) algorithms are good for small data sets; poor for larger ones. What constitutes "small" may change with time. Hash tables can give very nice performance, but they can waste a lot of memory with small data sets. I was trying to decide whether my data sets would be large enough to require a hash table; it seems they are.
|
|
|
|
|
Hello and please forgive me if this is not the right place to inquire, I am looking for a place to post a job for a .net developer who is not too senior, where could you recommend that i post this job? You can reach me at phyllis@panologic.com.
Job:
Software Engineer Windows Applications
Pano Logic is a venture-backed startup leading the Desktop Virtualization revolution. We are looking for an exceptional software engineer to build applications, user interfaces, and installers that are the "face" of Pano Logic's desktop virtual machine software.
• 0-4 years of C++-based application development experience
• Experience building high-quality Windows applications, user interfaces, and installers
• Knowledge of MFC, .NET, and Win32 system APIs
• Knowledge of Windows Installation technologies (Wix, Installshield, MSIs, etc)
• Experience building environments for unit tests, regressions, and nightly builds
• Experience with software build systems for Windows
• Computer Science/Engineering University Degree or equivalent
• Excellent interpersonal, verbal and written communication skills
The following would be an asset:
• Experience with device driver installation through Wix
• Scripting experience (Powershell, Perl, Python, shell scripting)
Please send resume to careers@panologic.com
|
|
|
|
|
|
"...looking for an exceptional software engineer..." with 0-4 years experience?
I read that as "we want somebody to do world-class work for entry-level pay".
Mark Salsbery
Microsoft MVP - Visual C++
![Java | [Coffee]](https://codeproject.freetls.fastly.net/script/Forums/Images/coffee.gif)
|
|
|
|
|
Mark Salsbery wrote: I read that as "we want somebody to do world-class work for entry-level pay".
I read that as a law-suit waiting to happen. In the UK you can no longer request specific numbers of years experience because it could be a round about way of trying to gauge a person's age and ageism is now illegal in a recruitment situation.
|
|
|
|
|
My resume goes all the way back to 1974. I think that makes it kind of obvious that I'm an old f*cker.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001
|
|
|
|
|
Mark Salsbery wrote: we want somebody to do world-class work for entry-level pay
Good luck to the OP to find a sucker.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
There is a job board[^] on this site. You should post there.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
PhyllisM wrote: Hello and please forgive me if this is not the right place to inquire, I am looking for a place to post a job for a .net developer who is not too senior
Well, I'm not sure how you could have missed the big green bar near the top of the site's home page.
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001
|
|
|
|
|
Hi,
I want to create a library for all the sql database operations.All other functions are working, but function for returning sqldatareader doesn't work.When I call this function from my page and try to access returned datareader object >it gives the error reader is closed. What to do???
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
