Thanks for the input. Feel free to make changes yourself
On Thu, Oct 18, 2018 at 5:54 PM MBond
wrote:
> OSR http://osr.vanillacommunities.com/
> MBond commented on Windows kernel XOR chain list
>
> 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 Mail 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
> >
>
> –
> Reply to this email directly or follow the link below to check it out:
> http://osr.vanillacommunities.com/discussion/comment/291012#Comment_291012
>
> Check it out:
> http://osr.vanillacommunities.com/discussion/comment/291012#Comment_291012
>