Interesting fast interop problem

Freqy

Hi all,

Summary: Can I pass out a linked list value type/pointer (my own class) from C++ to C# If not, what are the overheads/caveats involved in passing things around as void*s in C#

I'm trying to use C# as a basis for an audio application. I'm finding the speed is fine as long as I avoid a lot of object allocation/deallocation. By using a bit of C++ here and there I'm able to create and destroy critical objects in system memory rather than on the managed heap.

Recently in an attempt to further improve the speed of the application I ditched my ArrayList based buffers for a simple sorted linked list. I believed that the greater efficiency of the buffers would outweigh the hit incurred from creating and destroying list nodes. I was wrong.

So now down to the question. I'm looking for a way to implement the linked-list structure in C++ for use in C#. The main problem is that my major efficiency breakthrough hinges on passing the linked list nodes out directly to accessing classes so they can enumerate through all or part of the list.

As you can see it's a catch 22. I either use managed C++ to implement the class, giving me no actual gain, or I use unmanaged C++ and I have to pass things out through a managed wrapper. I'm not sure if I can do this, or whether it will be any faster in the end. C++ won't even let me create the circular reference that is fundamental to implementing a linked list!

Things are becoming too complicated and so far I haven't even matched the performance of the ArrayList, which has to copy itself as it grows or shift data when elements are removed. Any general suggestions on how to accomplish this task in other ways would be appreciated.

einaros

I'd be very careful in the assumption that the CLI generic containers and ArrayList are slow, as they should be regarded as quite optimized for their purpose. Writing your own native container, and using that in a C# application, will require quite a bit of support code. In addition, you should keep in mind that managed allocations are much faster than what you'd see with standard allocations done e.g. in stl containers, so you'd have to be prepared to write your own allocators (and not depend on frequent calls to new / delete). For containers, I just don't see any huge gain, and at least not anything justifying the amount of work it would be to get it to work. Optimizing certain algorithms through native libraries, however, can often be worth the work.

As for the circular reference, I don't understand what exactly is preventing you from doing this. Are you talking C++/CLI, or C++ (meaning native) Please be specific, as they are two different languages.

Freqy

Hi and thanks for the reply.

First of all, I'm not saying that Arraylist is slow, but if you use it as a sorted random access container it is incredibly inneficient, mainly due to the fact that it was never meant for that job. Copying elements back and forth can't be the best way to do this.

I'm creating my own container because none of the existing containers support fast merging, fast splitting, and storing the same key twice. If MS had provided *one* decent container class for C# I wouldn't be having this problem.

As for managed allocations, they are precisely what I need to avoid since they lock all CLI threads. I need to access up to 100 of these sorted lists about 50 times a second from up to four threads. Failing to do so in the allocated time causes failures at the real-time end (audio output).

The circular reference I'm talking about is the class ListNode { public ListNode next; } circular reference required to make a linked list. I'm remembering why I only use C++ when I have to.

Finally: managed vs unmanaged - that's the question I'm asking. At the base level the class must be native (or else I'd just implement it in C#). If I create a native C++ library to do this job, it will obviously store objects of type void*. How will I go passing in and out void*s and casting them all the time Can that even be done in C#

The further question is to do with returning a reference to a node in the list. It's really the same question again - if my nodes are unmanaged classes, how can I return/wrap these in an efficient manner

Looking forward to your response,

Aaron.

einaros

Freqy wrote:

I'm creating my own container because none of the existing containers support fast merging, fast splitting, and storing the same key twice. If MS had provided *one* decent container class for C# I wouldn't be having this problem. As for managed allocations, they are precisely what I need to avoid since they lock all CLI threads. I need to access up to 100 of these sorted lists about 50 times a second from up to four threads. Failing to do so in the allocated time causes failures at the real-time end (audio output).

Ok, those are reasons good enough for me. This essentially means that you need a native container, with your own allocators as a basis, though.

Freqy wrote:

The circular reference I'm talking about is the class ListNode { public ListNode next; } circular reference required to make a linked list. I'm remembering why I only use C++ when I have to.

I wouldn't be that quick to blame C++ (or C++/CLI, to be exact)

Freqy wrote:

Finally: managed vs unmanaged - that's the question I'm asking. At the base level the class must be native (or else I'd just implement it in C#). If I create a native C++ library to do this job, it will obviously store objects of type void*. How will I go passing in and out void*s and casting them all the time Can that even be done in C# The further question is to do with returning a reference to a node in the list. It's really the same question again - if my nodes are unmanaged classes, how can I return/wrap these in an efficient manner

What you could do is write native C++ code for the container itself, including all time-critical operations and native memory handling, and follow up by creating a middle tier in C++/CLI. In the C++/CLI code you can call into the native container to insert / extract data, utilize the container management functions (e.g. sort), and so forth. The C++/CLI tier should also do any necessary conversion needed between managed and unmanaged types.

Freqy

einaros wrote:

Ok, those are reasons good enough for me. This essentially means that you need a native container, with your own allocators as a basis, though.

That's right. I'm still a bit worried about previous experiences with converting between managed and unmanaged types, and trouble passing longs, but you're definitely on the right page. My new container is showing *lower* CPU usage, but is causing more audio dropouts than when I was using the ArrayList. I can only assume this is due to thread locking, since the profiler reveals no bottlenecks, and overcoming a previous problem like this had a dramatic effect. I sure hope I'm right as I embark on all this work, although this is only a hobby project and you only learn by challenging yourself, so...

einaros wrote:

I wouldn't be that quick to blame C++ (or C++/CLI, to be exact) ref class Foo { public: Foo^ next; }; Foo^ f = gcnew Foo(); f->next = f;

LOL yes, it's all coming back to me. Thanks for the refresher!

einaros wrote:

What you could do is write native C++ code for the container itself, including all time-critical operations and native memory handling, and follow up by creating a middle tier in C++/CLI. In the C++/CLI code you can call into the native container to insert / extract data, utilize the container management functions (e.g. sort), and so forth. The C++/CLI tier should also do any necessary conversion needed between managed and unmanaged types.

That almost sounds like a plan! I think I can see how it will work now:

value class fastList { ... }

this inside a managed wrapper that compiles a DLL (I use Express so no direct interop)

ref class managedFastList { ... }

with typed (or at least managed) operators and an enumerator to do the job of stepping through list nodes.

Thanks so much for your help, you're the greatest! If this is successful I'll add you to the contributors list.

http://sourceforge.net/projects/buzz-like