|
From: Robert W. <rj...@du...> - 2005-06-02 06:33:41
|
Hi all, I've updated my stack changing patch (and rearranged my web page a little.) http://www.durables.org/~rjwalsh/software/valgrind/ New in this version: * Added a version of the patch for Valgrind 3.0. * Made some minor modifications to make the 2.4 version look more like the resulting 3.0 version. * Incorporated some feedback from Nick about names. The user requests are now called VALGRIND_STACK_REGISTER and VALGRIND_STACK_DEREGISTER (instead of VALGRIND_STACK_NEW and VALGRIND_STACK_DELETE.) Still to do: * Document usage. * Measure performance impact. * Write tests for VALGRIND_STACK_DELETE and VALGRIND_STACK_CHANGE. * It could probably be made a bit more efficient by using an interval skip-list to store the registered stack data instead of a simple linked-list. After I see the performance impact, I'll decide about this. If you missed what this is all about, here's what I said in my last email: The patch allows user-land thread packages (e.g. coroutines) to deal with stack changes gracefully. Currently, Valgrind notices when %esp changes and uses a heuristic to figure out if that possibly means a thread change, or just that something large was pushed onto the stack. It often gets it wrong, since the heuristic is basically: =20 if delta %esp > some value, then assume a thread change =20 The problem is, it's hard to know what a good "some value" is since it depends a lot of how your program is written. =20 The change I've made allows you to register a memory range as a stack with Valgrind. Valgrind spots when %esp changes and checks if it's changed to a different registered stack. If it has, then it assumes a thread change. Regards, Robert. --=20 Robert Walsh Amalgamated Durables, Inc. - "We don't make the things you buy." Email: rj...@du... |
|
From: Nicholas N. <nj...@cs...> - 2005-06-02 16:15:40
|
On Wed, 1 Jun 2005, Robert Walsh wrote: > I've updated my stack changing patch (and rearranged my web page a > little.) > > Still to do: > > * Document usage. > * Measure performance impact. > * Write tests for VALGRIND_STACK_DELETE and VALGRIND_STACK_CHANGE. > * It could probably be made a bit more efficient by using an > interval skip-list to store the registered stack data instead of > a simple linked-list. After I see the performance impact, I'll > decide about this. I like this. It's a good approach to a problem we've had for a long time. --max-stackframe is also good but this seems necessary for the harder cases. It's a pretty clean addition too, which is good. Re performance, I wouldn't think it would make much difference to programs that don't use stack switching, since it only affects code that doesn't get run terribly often. It would be good to confirm that with numbers, though. N |
|
From: Robert W. <rj...@du...> - 2005-06-02 17:55:14
|
> Re performance, I wouldn't think it would make much difference to program= s=20 > that don't use stack switching, since it only affects code that doesn't=20 > get run terribly often. It would be good to confirm that with numbers,=20 > though. Right. That's why I didn't spend a huge amount of time optimizing it. If everyone's OK with this, I'll add some documentation, more tests and commit it to the 2.4 tree and 3.0 tree over the weekend. Regards, Robert. --=20 Robert Walsh Amalgamated Durables, Inc. - "We don't make the things you buy." Email: rj...@du... |
|
From: Jeremy F. <je...@go...> - 2005-06-02 20:27:12
|
Robert Walsh wrote:
>Still to do:
>
> * Document usage.
> * Measure performance impact.
> * Write tests for VALGRIND_STACK_DELETE and VALGRIND_STACK_CHANGE.
> * It could probably be made a bit more efficient by using an
> interval skip-list to store the registered stack data instead of
> a simple linked-list. After I see the performance impact, I'll
> decide about this.
>
>
(It's just a regular skip-list, not an interval skip-list.)
J
|
|
From: Robert W. <rj...@du...> - 2005-06-02 20:29:38
|
> > * It could probably be made a bit more efficient by using an > > interval skip-list to store the registered stack data instead of > > a simple linked-list. After I see the performance impact, I'll > > decide about this. > > > > > (It's just a regular skip-list, not an interval skip-list.) You mean that one that already comes with Valgrind? |
|
From: Jeremy F. <je...@go...> - 2005-06-02 21:25:27
|
Robert Walsh wrote:
>You mean that one that already comes with Valgrind?
>
Nick said:
> I have a patch that lets you use the regular skip-list as an interval
> skip-list, with just minor changes to the API. It's from a while ago,
> though.
A skiplist can represent non-overlapping intervals, but an interval
skiplist is a related but significantly more complex datastructure which
stores overlapping intervals and allows efficient stab queries (ie, all
intervals which overlap a point).
I'm just being pedantic. A skiplist containing intervals (like the
Segment list in 2.4) will do the job.
J
|
|
From: Nicholas N. <nj...@cs...> - 2005-06-02 21:31:07
|
On Thu, 2 Jun 2005, Jeremy Fitzhardinge wrote: >> I have a patch that lets you use the regular skip-list as an interval >> skip-list, with just minor changes to the API. It's from a while ago, >> though. > > A skiplist can represent non-overlapping intervals, but an interval > skiplist is a related but significantly more complex datastructure which > stores overlapping intervals and allows efficient stab queries (ie, all > intervals which overlap a point). Oh, yep, you're right. > I'm just being pedantic. A skiplist containing intervals (like the > Segment list in 2.4) will do the job. The 2.4 skiplist doesn't do intervals nicely, because you have to do the skiplist lookup and then another check "is this in the interval?" afterwards. My patch made this case nicer. N |
|
From: Nicholas N. <nj...@cs...> - 2005-06-02 20:56:53
|
On Thu, 2 Jun 2005, Jeremy Fitzhardinge wrote: > (It's just a regular skip-list, not an interval skip-list.) I have a patch that lets you use the regular skip-list as an interval skip-list, with just minor changes to the API. It's from a while ago, though. N |
|
From: Julian S. <js...@ac...> - 2005-06-03 02:24:45
|
> If everyone's OK with this, I'll add some documentation, more tests and > commit it to the 2.4 tree and 3.0 tree over the weekend. Looks ok, but .. - I'd prefer to stick with the simple linked list until you have performance data showing it to be a problem - Putting it in m_aspacemgr is troublesome because it uses VG_(arena_malloc) and therefore exacerbates the existing circular dependency between m_aspacemgr and m_mallocfree. Moves are afoot to break that cycle, and this would set it back. What would be helpful is if you could add a comment to the additions to m_aspacemgr giving an overview of what the code actually does. - Could you add documentation to the XML sources describing the new client reqs? It occurs to me the first two points might be solved by getting rid of the linked list and dynamic allocation of struct _Stack, and instead having a fixed sized statically allocated array, which, if you kept it in order, could give you O(log N) searching. J |
|
From: Robert W. <rj...@du...> - 2005-06-03 21:02:10
|
> - I'd prefer to stick with the simple linked list until you have > performance data showing it to be a problem That was the plan. > - Putting it in m_aspacemgr is troublesome because it uses > VG_(arena_malloc) and therefore exacerbates the existing circular > dependency between m_aspacemgr and m_mallocfree. Moves are > afoot to break that cycle, and this would set it back. > > What would be helpful is if you could add a comment to the > additions to m_aspacemgr giving an overview of what the code > actually does. Hmm. OK then. One way to solve this would be to make a stack module (m_stack, say.) What I'd like to do for now is push the changes back as is with a comment as you suggest. Later, this code can be moved to it's own module. > - Could you add documentation to the XML sources describing > the new client reqs? Yes. I'll be doing docs for 2.4 and 3.0 this weekend. > It occurs to me the first two points might be solved by getting > rid of the linked list and dynamic allocation of struct _Stack, > and instead having a fixed sized statically allocated array, > which, if you kept it in order, could give you O(log N) searching. The problem with that is that you never know how many coroutines you might have. I can envisage cases with thousands or hundreds of thousands of coroutines. In our scenario, we'll definitely have thousands as a routine case and upwards of 10000 in extreme cases. I prefer allocating this stuff dynamically. Regards, Robert. |
|
From: Jeremy F. <je...@go...> - 2005-06-03 06:17:33
|
Nicholas Nethercote wrote:
> The 2.4 skiplist doesn't do intervals nicely, because you have to do
> the skiplist lookup and then another check "is this in the interval?"
> afterwards. My patch made this case nicer.
I remember your patch which made "exactly equal" searches easier,
compared to the original "equal or after" semantics; I put some extra
search functions to make all this easier. I don't remember seeing
anything about intervals though. Did I overlook it?
J
|
|
From: Nicholas N. <nj...@cs...> - 2005-06-03 13:37:36
Attachments:
vg_skiplist.c
diff
|
On Thu, 2 Jun 2005, Jeremy Fitzhardinge wrote: > I remember your patch which made "exactly equal" searches easier, > compared to the original "equal or after" semantics; I put some extra > search functions to make all this easier. > I don't remember seeing anything about intervals though. You could do intervals with it because the comparison function got the whole node to compare against the key being searched for, not just the key of the node. So you could use both the address and the size in the comparison, eg if (addr <= key && key < addr+size) return True; IIRC that means you don't need each of Find_Before, Find_After and Find_Exact, because Find can do it all. Or something like that, it was a while ago. I'm not sure if I sent it to the list. I've attached the vg_skiplist.c file, which you can diff against the current one, and also an old diff against the rest of the repo which showed how I was using it. I never got that working correctly, though. Nick |