|
From: Konstantin S. <kon...@gm...> - 2008-01-15 09:24:56
|
Hi Julian, all,
I found out that ~85% of helgrind's time (on one of my tests) is spent in
the following loop:
static void shadow_mem_make_NoAccess ( Thread* thr, Addr aIN, SizeT len )
...
/* FIXME: don't iterate over the complete lock set */
HG_(initIterFM)( map_locks );
while (HG_(nextIterFM)( map_locks,
(Word*)&gla, (Word*)&lk )) {
...
Average number of iterations of this loop is ~5600, which is the number of
locks in the entire program (right)?
Would you suggest a way to rewrite this loop so that it does not iterate
over all locks?
Can we do a binary search in map_locks instead of iterating it?
I mean, most of the time the deallocated memory contains no locks. We can
check if the is the case by binary searching map_locks, can't we?
We will need to extend hg_wordfm.c with few more methods...
What do you think?
Thanks,
--kcc
|
|
From: Julian S. <js...@ac...> - 2008-01-15 09:37:39
|
> I found out that ~85% of helgrind's time (on one of my tests) is spent in
> the following loop:
Yes. I saw a similar problem running OOo on Helgrind.
> ...
> /* FIXME: don't iterate over the complete lock set */
> HG_(initIterFM)( map_locks );
> while (HG_(nextIterFM)( map_locks,
> (Word*)&gla, (Word*)&lk )) {
> ...
>
> Average number of iterations of this loop is ~5600, which is the number of
> locks in the entire program (right)?
> Would you suggest a way to rewrite this loop so that it does not iterate
> over all locks?
> I mean, most of the time the deallocated memory contains no locks. We can
> check if the is the case by binary searching map_locks, can't we?
> We will need to extend hg_wordfm.c with few more methods...
> What do you think?
I think you are correct. I had thought about this before but did
not implement it.
Idea is to change HG_(initIterFM) so that it takes a key value:
void HG_(initIterFM)( WordFM* fm, Word start_at )
so that the first call to HG_(nextIterFM) produces (in "gla") the first
value >= start_at. So the loop now looks like this:
/* To scan memory address range s_start to s_end: */
HG_(initIterFM)( s_start );
while (True) {
Bool b = HG_(nextIterFM)( map_locks, (Word*)&gla, (Word*)&lk );
if (!b) break; /* no more entries in map */
if (gla > s_end) break; /* finished s_start .. s_end range */
/* do stuff with (gla, lk) */
}
if you see what I mean.
So the only new method is to change HG_(initIterFM) (maybe better to
make a new one, HG_(initAtIterFM)). That requires to understand the
FM iteration mechanism. Not difficult, but I did not find the time
to study it.
J
|
|
From: Konstantin S. <kon...@gm...> - 2008-01-15 09:41:25
|
> > > So the only new method is to change HG_(initIterFM) (maybe better to > make a new one, HG_(initAtIterFM)). That requires to understand the > FM iteration mechanism. Not difficult, but I did not find the time > to study it. > > J > If you don't mind, I'll implement this one and send you the patch. --kcc |