Yes names like xxxInterlockedxxx should actually be interlocked – as opposed to software lock based ?
Also, on Amazon I can buy RAM at the rate of about $10 per GB. This means that the ‘value’ of using code like this that saves 8 bytes per entry, is only significant when the size of the list is absolutely enormous – say 100 million items or greater. But this is absolutely exactly the kind of list that should not be stored using this kind of structure so it is kind of a catch 22.
Of much more interest is the relative speed of the operations
In the insert path, you have one branch and either two assignments or three + 3 xors. A standard implementation can have zero branches and 4 assignments (two of which can be done via interlockedCompareExchange).
In the remove path, you have two branches, two assignments and one or 3 xors. A standard implementation can have zero branches and 3 assignments (two of which can be done via interlockedCompareExchange).
The branches are going to kill your performance, but I think if you work at it you can eliminate them. Usually a good way to eliminate the branches is to make the list circularly linked to an ‘anchor’ or ‘root’ node so all of the operations always have both a previous and next node – but that probably does not work well here
Sent from Mailhttps: for Windows 10
________________________________
From: Jamey_Kirby
Sent: Thursday, October 18, 2018 5:16:57 PM
To: MBond
Subject: Re: [NTDEV] Windows kernel XOR chain list
OSR http://osr.vanillacommunities.com/
Jamey_Kirby commented on Windows kernel XOR chain list
I remember reading about xor chaining in a Dr. Dobb’s article in the late
80’s or early 90’s, and have always wanted to find a use for one.
Tim: You are correct, I only implemented a deque (add to tail, remove from
head), as that was my immediate requirement. Yes, I do want to implements a
fuller set of functions to traverse and such, but, as you mentioned, those
are expensive operations, and probably not very practical for large lists.
Adding RemoveTail, and InsertHead are trivial.
Peter: Yes, I considered using different naming, or do something more like
the kernel does (disable interrupts, etc.). I am not adverse to others
contributing to the code either
Phil: I did put two functions in the header. Good suggestion though. The
interlocked versions are probably best left as functions.
Thanks for the feedback.
On Thu, Oct 18, 2018 at 4:57 PM Peter_Viscarola_(OSR)
wrote:
> OSR https://community.osr.com/
> Peter_Viscarola_(OSR) commented on Windows kernel XOR chain list
>
> First… Thank you, Jamey, for once again openly sharing your work with
> the Windows driver development community. That’s darn nice of you.
>
> Now… Being basically ignorant, I’m not going to claim I understand how
> this thing works.
>
> But I did notice that there’s an ExInterlockedRemoveHeadXorList
> implementation… and I wanted to note that this is not similar to the
> standard Windows ExInterlockedRemoveHeadList function in that it can only
> be called at IRQL <= DISPATCH_LEVEL. I think using the same naming
> convention, but a very different set of functionalities and constraints is
> unwise.
>
> I always wanted to point out that this implementation unfortunately lacks
> SAL annotations. Which is unfortunate, as these types of projects are cool
> ways to show people what SAL is about and how it should be used.
>
> Peter
>
> –
> Reply to this email directly or follow the link below to check it out:
> https://community.osr.com/discussion/comment/291010#Comment_291010
>
> Check it out:
> https://community.osr.com/discussion/comment/291010#Comment_291010
></https:>