Messages in this thread | | | From | Keith Owens <> | Subject | Re: [PATCH] Decrease hash table memory overhead | Date | Tue, 01 Aug 2000 23:06:27 +1000 |
| |
On Tue, 1 Aug 2000 13:38:16 +0100 (BST), Mark Hemment <markhe@veritas.com> wrote: > I've attached a patch (against 2.4.0-test5) for the page cache, which >demonstrates a technique to reduce the length of re-searching of a chain >after its guarding lock has been temporarily dropped (say, for a blocking >operation), and the re-search is expected to fail. >[snip] > By inserting a marker (cookie) as the first object (after the original >search and while the guarding lock is still held) gives a well known >point at which to terminate a subsequent search (assuming it doesn't match >before reaching the marker). >[snip]
There is a method which may give almost the same performance boost but is much easier to use. Associate an update counter with each chain head. Every add or delete on that chain increments the counter, the lock is held so no need for atomic_t counters. If the chain head is being updated at the same time then the counter update is almost free, assuming the head and the counter are in the same cache line.
The sequence is then :-
start: get_lock(); search_chain(); if (entry not found) { save_chain_update_counter(); drop_lock(); allocate_new_object(); format_new_object(); get_lock(); If (current_chain_counter != saved_chain_counter) { drop_lock(); free_new_object(); goto start; } insert_object(); ++chain_counter(); } entry_exists_do_something:
The cost is obviously one extra word per chain head. The benefit is that the algorithm is completely independent of the data on the chain. Assuming the common case is no updates to this chain while the lock was released, it removes the second scan of the chain.
Freeing the new object on restart simplifies the code, no need to remember if you already have a pre-formatted object and no need to free any pre-formatted object if the entry exists on the second pass. OTOH, if the overhead of freeing is too high (which depends on the frequency of concurrent updates) then more complex code could be used to remember any pre-formatted object.
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |