| Summary: | Implement HT_remove_at_Iter to avoid quadratic auto free pool algorithm | ||
|---|---|---|---|
| Product: | [Developer tools] valgrind | Reporter: | Ruurd Beerstra <ruurd.beerstra> |
| Component: | general | Assignee: | Julian Seward <jseward> |
| Status: | RESOLVED FIXED | ||
| Severity: | normal | CC: | philippe.waroquiers |
| Priority: | NOR | ||
| Version: | 3.12 SVN | ||
| Target Milestone: | --- | ||
| Platform: | unspecified | ||
| OS: | All | ||
| Latest Commit: | Version Fixed In: | ||
| Bug Depends on: | |||
| Bug Blocks: | 370941 | ||
| Attachments: |
Add HT_remove_at_iter function
slightly reworked patch, with an alternative implementation of HT_remove_at_Iter |
||
Created attachment 101438 [details]
slightly reworked patch, with an alternative implementation of HT_remove_at_Iter
Find attached a slightly reworked patch (in m_hashtable.c) :
Instead of maintaining in HT_Next iterPrevNode and iterPrevChain,
the previous chain and previous node are calculated in VG_(remove_at_Iter).
This has no performance impact on existing usage of VG_(HT_Next).
On the performance test of the auto free pool, this is also slightly faster (a few percents).
fixed in revision 16041 (reworked implementation applied, to ensure no impact on existing hashtable uses) |
Created attachment 101328 [details] Add HT_remove_at_iter function The HT_Next iterator can be used to find items to be removed from a list using HT_remove. However, after the remove the iterator is considered "not OK" and so needs to be restarted, leading to quadratic behavior. Attached patch adds a HT_remove_at_Iter function which removes the current item from the table, whilst leaving the iterator in the proper state so HT_Next will return the item after the just-removed one. The function is used in free_mallocs_in_mempool_block which is now much simplified and faster, but can be used in other parts of memcheck as well. The leak-autofreepool.c tst has been updated with a new test-case 6, which tries to stress the malloc-list search & remove algorithm. I've tested it manually by setting the verbosity level high and observing that the HT_remove_at_Iter function removes some (but not all) entries and that all tests report the expected results.