Re: Roll your own std::vector ???

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance


"Chris Mullins" <cmullins@xxxxxxxxx> wrote in message
news:%23CTcR26IHHA.1276@xxxxxxxxxxxxxxxxxxxxxxx
"Peter Olcott" <NoSpam@xxxxxxxxxxxxx> wrote

The most time critical aspect of my application spends about 99% of its time
comparing elements in one array to elements in other arrays. This subsystem
can tolerate no additional overhead at all, having a real-time constraint of
1/10 second.

So why are you so worried about the "adding into a list" performance case? It
seems as if you would be much more worried about traversal and comparision,
rather than just inserting.

Also, if you are inserting into an array, (be it List<>, or something else)
you're always going to have hits while it resizes the array - as long as
you're doing insertions or deletions, this is going to be a problem. Use a
linked lists. You gotta pick the right datastructure for your problem.

To further confuse issues, if this is the most time critical piece of your
application, you need to spend some very serious time looking at a better
algorithm. You're going to want to partition your comparisions across
processors using multiple threads (possibly setting affinity), and do so in a
way that avoids locking in the general case, and is intelligent about use of
processor cache (aka: avoids blowing the cache constantly).

It works fine now in native C++, I just don't want the port to .NET to break
this performance. Unless I can know in advance that .NET will not break this
performance I don't have time to learn .NET.


Parallel Algorithms are going to be (well, should be) a major part of your
solution. Depending on your use case and processor counts, you may also want
to look into the various lock-free list implementations.

The simple thing to do is to use dual core processors and allocate one core to
this process, since this process must achieve its 1/10 second real time limit
concurrently with other processes. In actuality this probably will not be
required for most applications because most of the time the other process will
not be using very much CPU time during the execution of this process.



These problems are in no way language specific. C / C++ / Java / C# / VB.Net
will all do a fine job. It's really up to you to determine the best algorithm
given your problem.

--
Chris Mullins, MCSD.NET, MCPD:Enterprise
http://www.coversant.net/blogs/cmullins




.

Relevant Pages

  • Re: Roll your own std::vector ???
    ... time comparing elements in one array to elements in other arrays. ... Also, if you are inserting into an array, ... linked lists. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Roll your own std::vector ???
    ... comparing elements in one array to elements in other arrays. ... arrays aren't the same as lists ... So the benchmark you've been basing your 500% figure on is irrelevant ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Dict sharing vs. duplication
    ... array to enforce unique keys and I use lists to enforce order. ... API in a page or two of Tcl code, it isn't so much a missing feature ... OpenACS database API which creates a new specialized data structure, ...
    (comp.lang.tcl)
  • Re: Translating python to scheme
    ... Scheme has mutation, and there are reasons to use it. ... confusing when considering a 2d array. ... in other languages: Lisp Lists and Vectors. ...
    (comp.lang.scheme)