Re: LinkedList since .NET 2 - C# Discussion Boards

Alan Balkany14-Apr-11 4:13

Alan Balkany

14-Apr-11 4:13

"Does anybody has a good scenario as an example where they'd need LinkedList?"

It's useful when you don't know the size you'll need in advance, you're doing mostly sequential processing, and want fast performance. Insertions/deletions in the middle are fast. Its drawbacks are:

1. Memory overhead from pointers,
2. It's slow for randomly accessing elements in the middle, i.e. the nth element. Sorting is very slow.
3. No locality of reference, i.e. when you access element n, element n + 1 probably isn't in the cache, as it would be with an array or List.

You could use a List, which has fast indexed access (nth element) but there are some drawbacks:

1. When you exceed its initial allocation, it copies the WHOLE list to a new array. This is slow.
2. The new array is double the size of the previous one, so you may end up allocating twice the storage you need.
3. Insertions and deletions in the middle are slow, since many elements have to be moved.

You have to use the right tool for the job.

devvvy14-Apr-11 23:03

devvvy

14-Apr-11 23:03

Yes I know if you don't know capacity ahead of time List would reallocate. What I am asking is, real life scenario.

I got by using Dictionary and List for the most part, some SortedDictionary - and all done within polynomial time.

Never had a business/tech scenario where I'd need link list with slow retrieval time.

For instance, trade tables, dictionary with tradeId as key be better.

Or execution queue - also been using dictionary with execId as key. Never a linkedList.

Any real/practical scenario?

dev

Pete O'Hanlon14-Apr-11 23:37

Pete O'Hanlon

14-Apr-11 23:37

If you're wanting to hold a sparse matrix, a linked list is an ideal structure. I've used them before to hold massively dimensioned matrices (e.g. for chemical engineering based systems). That was in C++ though - I am less than whelmed by the .NET implementation.

Forgive your enemies - it messes with their heads

My blog | My articles | MoXAML PowerToys | Mole 2010 - debugging made easier - my favourite utility

devvvy14-Apr-11 23:42

devvvy

14-Apr-11 23:42

hum... good point... which brings me to the thought that there's no such thing as sparse list.

thanks

dev

Alan Balkany15-Apr-11 3:24

Alan Balkany

15-Apr-11 3:24

"Any real/practical scenario?"

In an upcoming project, I have a data stream coming in, and I "clump" elements for later processing. I don't know in advance how many clumps I'm going to have, and the later processing is only going to go through them sequentially.

I'm planning on using a linked list for this.

devvvy16-Apr-11 16:50

devvvy

16-Apr-11 16:50

hum... sequential access - why not a SortedList<int, Stream>? with key "Int" (for example DataId)

dev

Application Crashes during AppDomain.Unload [modified]

Alan Balkany18-Apr-11 4:07

Alan Balkany

18-Apr-11 4:07

1. A SortedList maintains an array for the elements like the generic List, so has the same disadvantages: The WHOLE list must be recopied every time it exceeds its capacity, which is slow, and which may waste space.

2. In addition, the SortedList maintains another copy of the the elements' keys for indexing, which takes even more space.

3. In my case, I don't need sorting, so this would be overhead for me, both in the time to keep it sorted, and in the extra memory required for the indexing.

Benny_Lava13-Apr-11 3:44

13-Apr-11 3:44

Hi,

I have a very strange problem, i have multiple AppDomains (plugin system).

Now at one point i raise an event from one of the plugin domains and the main AppDomain catches the event and calls another function in a seperate thread that Unloads the calling AppDomain.

The first thing that came to my mind is that the plugin domain somehow became the main application domain but it didn't i checked before the culprit line below for AppDomain.FriendlyName and it was different than the main application domain.

code:

private void UnloadDevicePluginDomain(DevicePlugin d)
        {
            Guid id = Guid.NewGuid();

            try {
                lock(locker_) {
                    if(d == null)
                        return;
                    id = d.DevicePluginId;
                    if(d.PluginDomain != null) {
                        //--Just to be on the safe side call plugin Dispose before App domain unload
                        if(d.DeviceInterface != null) {
                            d.DeviceInterface.Dispose();
                        }

                        if(d.WatchDogTimer != null)
                            d.WatchDogTimer.Dispose();

                        d.PluginDomain.UnhandledException -= new UnhandledExceptionEventHandler(DevicePluginCrashed);

                        AppDomain.Unload(d.PluginDomain);   //THE WHOLE APPLICATION CRASHES AT THIS LINE
                        devicePlugins_.Remove(d);
                    }
                }
            } catch (Exception ex) {
               // DOES NOT COME TO THIS PART
            }
        }

So the weird thing is that there is an exception handler and the line nonetheless crashes the whole application.

Any help greatly appreciated.

Thanks.

-- Modified Wednesday, April 13, 2011 3:39 PM

gavindon13-Apr-11 3:56

gavindon

13-Apr-11 3:56

I don't have an answer for ya but to save you from the pros slapping your wrist. put the code in a code block so they can read it easier.. and then they wont have to focus their answer on your code not being in a block Big Grin | :-D

Programming is a race between programmers trying to build bigger and better idiot proof programs, and the universe trying to build bigger and better idiots, so far... the universe is winning.

Benny_Lava13-Apr-11 9:41

13-Apr-11 9:41

Hehe,

Thanks, I stand corrected and my post also... Smile | :)

Not Active13-Apr-11 3:57

Not Active

13-Apr-11 3:57

Please format your code using the code block toolbar item.

Have you tried not removing the UnhandledException handler to see if the Exception is caught.

Don't know if this is useful, it's an old article
Application Suite Template[^]

I know the language. I've read a book. - _Madmatt

Benny_Lava13-Apr-11 9:25

13-Apr-11 9:25

Hi,

Thanks for your reply, i'll try removing the UhandledException unsubscription.

P.S
Sorry i didn't put the code in a code block, I know about it just forgot to use it Smile | :)

BobJanova13-Apr-11 6:18

BobJanova

13-Apr-11 6:18

Now at one point i raise an event from one of the plugin domains and the main AppDomain catches the event and calls another function in a seperate thread that Unloads the calling AppDomain.

That sounds like the problem to me. What's probably happening is the domain is getting unloaded while its event handler is still running, and that's confusing the CLR at a level below your exception handling.

(What do you mean by 'crash', by the way?)

If you want plugins to be able to unload themselves, I think you will have to set a timer in that event handler so that the plugin domain is no longer doing stuff when you try to unload it. (And obviously, once the plugin raises that event, it should also kill any threads it spawned and not do any more processing, since it's issuing a suicide note by raising it.)

Benny_Lava13-Apr-11 9:38

13-Apr-11 9:38

Hi,

That sounds like the problem to me. What's probably happening is the domain is getting unloaded while its event handler is still running, and that's confusing the CLR at a level below your exception handling.

Yes, that crossed my mind the minute the bug appeared, but the event handler adds the method to a method execution queue I designed and that queue is run in a separate thread, so the event handler 100% exits.

By crash I mean when i'm in debugging mode after i press step over over the AppDomain.Unload the debugging session ends and the application literally crashes... Smile | :)

The plugins do not unload themselves, a dedicated method execution queue runned by a thread that is created in the main AppDomain terminates them by processing the method I posted in the original post.

Thank you for your quick reply.

BobJanova13-Apr-11 10:57

BobJanova

13-Apr-11 10:57

I'm not sure if you can unload a plugin from a different thread to the one that spawned it, come to think of it.

Running a queue in a separate thread is actually a really good way of having the unload happen before it should, unless you're applying a delay or doing some cross-domain interlocking.

I also agree with the other poster who said that you could try not unhooking the UnhandledException event handler. It should go out of scope and disappear anyway when the plugin reference is lost.

Benny_Lava13-Apr-11 22:06

13-Apr-11 22:06

Hi,

After a session of debugging using all advices I collected, here are my findings (So everybody can learn from my mistakes... Smile | :)

)

-A plugin can be unloaded from a different thread (other thread then the one that spawned it
-The problem was that I also handled UnhandledException event of the AppDomain, and a series of unfortunate events happened:

*I have 2 mechanisms for protecting my core system from plugins:
1. A watchdog timer mechanism that terminates a plugin if the plugin hasn't responded (raised an watch dog timer event) for a certain period of time
2.A UnhandledException event handler for when an unhandled error occurs in the plugin, and in that event i call UnloadPlugin function and remove the plugin from the core system

So a plugin spawned an unhandled exception the same time the watchdog timer called UnloadPlugin function... And in the UnhandledException handler it tried to use data and unload an already unloaded AppDomain

So the solution is to develop some kind of synchronization mechanism so if one request for termination comes that no other request are processed.

So the bottom line is "Threads are evil" Wink | ;)

Thanks for your help.