Messages in this thread |  | | | Date | Thu, 16 Jul 2009 15:12:37 +0800 | | Subject | Re: [RESEND PATCH 0/11] kernel:lockdep:replace DFS with BFS | | From | Ming Lei <> |
| |
2009/7/16 Peter Zijlstra <a.p.zijlstra@chello.nl>: > > I've asked several times to comment on the removal of that generation > count DaveM did. Is that a normal part of DFS, or was that an > optimization on top particular to this problem, can something similar be > done for BFS, etc.
DFS uses generation count DaveM did to decide if a class is visted, and BFS uses bitmap to mark a class is visted or not and the extra efficiency loss is
bitmap_zero(bfs_accessed, MAX_LOCKDEP_ENTRIES);
before staring each BFS.
On most of ARCH, bimap_zero can be optimizied to only consume very few instructions, can't it?
It seems bitmap is more easily used in BFS than generation count.
> > Other than that it does seem to hold up, I've got the patches running on > my laptop. Don't worry they're not getting lost.
Great.
-- Lei Ming
|  |