|
From: David K. <dw...@de...> - 2006-01-23 05:55:16
|
Hi all, I am working on implementing compressed vbits as described on the project suggestions page. So far I have it, I think, working without any of the load/store optimizations (VG_DEBUG_MEMORY =3D 2). It doesn't look too terribly slow compared to the uncomrepessed, unoptimized case. I am cautiously optimistic that the slowdown won't be too large once the load/store optimixations. I placed the work in progress up at http://people.debian.org/~dwhedon/compressed-vbits/ for the curious. The next step is to implement the load/stores so I can turn VG_DEBUG_MEMORY off and see what sort of performance we get.=20 Hopefully I can get to doing that in the next week or so. -David |
|
From: Nicholas N. <nj...@cs...> - 2006-01-23 09:40:51
|
On Sun, 22 Jan 2006, David Kimdon wrote: > I am working on implementing compressed vbits as described on the > project suggestions page. So far I have it, I think, working without > any of the load/store optimizations (VG_DEBUG_MEMORY = 2). It doesn't > look too terribly slow compared to the uncomrepessed, unoptimized > case. I am cautiously optimistic that the slowdown won't be too large > once the load/store optimixations. I placed the work in progress up > at > http://people.debian.org/~dwhedon/compressed-vbits/ for the curious. Ah. The good news is you've made a good start! The bad news is that I have a 90%-complete implementation already. It's in the COMPVBITS branch (use svn co svn://svn.valgrind.org/valgrind/branches/COMPVBITS to check it out). It's actually quite a bit faster (typically 15%-ish?) than the current head, because the fast cases are more streamlined. The plan is to merge it into the trunk fairly soon. Sorry about this, I should have removed that project from the website. I've done that now. Looking at your code, I see you have one secondary V bits table per SecMap, which is an interesting idea; I have a single table for everything. Your approach makes for faster lookups, but the garbage collection of stale nodes becomes more complicated... hmm, interesting. Nick |
|
From: David K. <dw...@gm...> - 2006-01-24 06:08:37
|
On 1/23/06, Nicholas Nethercote <nj...@cs...> wrote: > On Sun, 22 Jan 2006, David Kimdon wrote: > The good news is you've made a good start! Thanks for the support :-) > > The bad news is that I have a 90%-complete implementation already. It's That's actually good news too, depending on how we look at it, I wasn't really looking forward to doing all the load/store routines . . . > in the COMPVBITS branch (use svn co > svn://svn.valgrind.org/valgrind/branches/COMPVBITS to check it out). > It's actually quite a bit faster (typically 15%-ish?) than the current > head, because the fast cases are more streamlined. The plan is to merge > it into the trunk fairly soon. cool, I will take a look. > Looking at your code, I see you have one secondary V bits table per > SecMap, which is an interesting idea; I have a single table for > everything. Your approach makes for faster lookups, but the garbage > collection of stale nodes becomes more complicated... hmm, interesting. I wonder if we even need to collect them. In my current implementation I never remove from the OSet. The nodes _could_ be removed when the avbits changed to allow it, but are there so few of them that we can just leave them to rot? |
|
From: Nicholas N. <nj...@cs...> - 2006-01-24 22:10:15
|
On Mon, 23 Jan 2006, David Kimdon wrote: >> The bad news is that I have a 90%-complete implementation already. It's > > That's actually good news too, depending on how we look at it, I > wasn't really looking forward to doing all the load/store routines . . (: This stuff is pretty gnarly. >> Looking at your code, I see you have one secondary V bits table per >> SecMap, which is an interesting idea; I have a single table for >> everything. Your approach makes for faster lookups, but the garbage >> collection of stale nodes becomes more complicated... hmm, interesting. > > I wonder if we even need to collect them. In my current implementation > I never remove from the OSet. The nodes _could_ be removed when the > avbits changed to allow it, but are there so few of them that we can > just leave them to rot? I considered that, but decided against it because it could lead to slow-downs and space leaks in bad cases. I'm currently writing some documentation about the compressed V bits, I've attached the part about the secondary V bits table in case it's of interest. It may still be possible to have one sec-V-bits table per sec-map and still do the same basic garbage collection. Nick |
|
From: Nicholas N. <nj...@cs...> - 2006-01-24 22:23:20
Attachments:
sec
|
On Tue, 24 Jan 2006, Nicholas Nethercote wrote: > I'm currently writing some documentation about the compressed V bits, I've > attached the part about the secondary V bits table in case it's of interest. I've actually attached it this time. N |
|
From: David K. <dw...@de...> - 2006-02-20 01:45:44
|
It looks like the COMPVBITS branch isn't tracking VEX head, which version of VEX should I be using to try out the COMPVBTIS branch? Thanks, David |
|
From: Julian S. <js...@ac...> - 2006-02-20 01:56:24
|
On Monday 20 February 2006 01:45, David Kimdon wrote:
> It looks like the COMPVBITS branch isn't tracking VEX head, which
> version of VEX should I be using to try out the COMPVBTIS branch?
Yeh, I was trying to shake out a 64-bit bug just now and also had
difficulties on checkout. Eventually I did this:
svn co -r "{2006-01-12}" svn://svn.valgrind.org/valgrind/branches/COMPVBITS \
cvbit
cd cvbit
rm -rf VEX
svn co -r "{2006-01-12}" svn://svn.valgrind.org/vex/trunk VEX
J
|
|
From: David K. <dw...@de...> - 2006-02-21 21:42:05
|
On 2/19/06, Julian Seward <js...@ac...> wrote: > Yeh, I was trying to shake out a 64-bit bug just now and also had > difficulties on checkout. Eventually I did this: ok, thanks, that builds for me. If there aren't any real vex related changes in COMPVBITS then we never have to merge the vex valgrind/trunk changes into COMPVBITS. We will just merge COMPVBITS back into trunk when it is done. In that case perhaps we can decide on which version of VEX the COMPVBITS branch will use, and add that to the externals property so it gets pulled in automatically? Something like the following will lock VEX to the revision that Julian found works (it builds for me as well): Property changes on: ___________________________________________________________________ Name: svn:externals - VEX svn://svn.valgrind.org/vex/trunk + VEX -r1535 svn://svn.valgrind.org/vex/trunk |
|
From: Nicholas N. <nj...@cs...> - 2006-02-21 22:18:30
|
On Tue, 21 Feb 2006, David Kimdon wrote: > If there aren't any real vex related changes in COMPVBITS then we > never have to merge the vex valgrind/trunk changes into COMPVBITS. > We will just merge COMPVBITS back into trunk when it is done. Yes. COMPVBITS is now ready for the trunk. I might get to merging it in the next week, if not then I won't have time until the end of March. Either way it should make it into 3.2.0. > In that case perhaps we can decide on which version of VEX the > COMPVBITS branch will use, and add that to the externals property so > it gets pulled in automatically? > > Something like the following will lock VEX to the revision that Julian > found works (it builds for me as well): > > Property changes on: > ___________________________________________________________________ > Name: svn:externals > - VEX svn://svn.valgrind.org/vex/trunk > > + VEX -r1535 svn://svn.valgrind.org/vex/trunk That would be fine by me. N |
|
From: Nicholas N. <nj...@cs...> - 2006-04-06 14:00:39
|
On Tue, 21 Feb 2006, David Kimdon wrote: >> Yeh, I was trying to shake out a 64-bit bug just now and also had >> difficulties on checkout. Eventually I did this: > > ok, thanks, that builds for me. > > If there aren't any real vex related changes in COMPVBITS then we > never have to merge the vex valgrind/trunk changes into COMPVBITS. > We will just merge COMPVBITS back into trunk when it is done. > In that case perhaps we can decide on which version of VEX the > COMPVBITS branch will use, and add that to the externals property so > it gets pulled in automatically? > > Something like the following will lock VEX to the revision that Julian > found works (it builds for me as well): > > Property changes on: > ___________________________________________________________________ > Name: svn:externals > - VEX svn://svn.valgrind.org/vex/trunk > > + VEX -r1535 svn://svn.valgrind.org/vex/trunk COMPVBITS was merged into the trunk a little while ago so this problem should be gone. Nick |