swap table trimming, take 2

[shentino]

First, as a gesture of candor, I already failed once to implement this feature in a sustainable manner, so let that be said.

Having said that I think the idea still has merit, and at the very least it's an opportunity to save memory and disk space.

My mistake last time was falling asleep at the wheel and not keeping the feature maintained, and lacking both the confidence and diligence to keep the feature alive. Further investigation seems to indicate a combination on my part of being somewhat lazy and lacking courage in the face of failure.

Since the overhead involved is an simple qsort followed by a couple of allocations and pointer juggles every full snapshot, IIRC, compared to the sustained overhead of consuming memory and disk space, I think this feature is still worthwhile.

Who should bear the burden of actually implementing this feature is another story.

[dworkin]

commit e1b66963b1898433c0ddd9ba10b1830dfa329c23
Author: Raymond Jennings <shentino@gmail.com>
Date:   Fri Feb 27 18:59:23 2015 -0800

    remove swap trimming

    This patch removes swap table trimming since it doesn't really do much good.

Why did you change your mind?

[shentino]

I forget exactly but I think I was feeling discouraged after object table trimming failed.

Then after you removed the dead code I left behind I never really saw fit to revisit the issue until now.

For reasons I don't really think are appropriate to go into in public my self confidence isn't really that good, but I can say that it probably has nothing to do with any supposed lack of competence on my part as a programmer.

[shentino]

Oh!

Why did I change my mind, not why did I remove it.

I realized that the benefit of a one time qsort + reallocation is very likely to be outweighed by a sustained memory and disk burden, and also that my depression biased opinion at the time I removed the feature was probably not credible.

[dworkin]

Swap table trimming, as you implemented it, genuinely doesn't do much. Free sectors at the end of the map are eliminated from the free list and the swap sectors in the free list are sorted, that's it. One sector that remains allocated at the end will continue to prevent the swap map from shrinking. If that is really so important, then you should remap all used sectors, not just the free list.

[dworkin]

Let's take a look at how much might be wasted and saved by cleaning up the swap map properly (reallocating all sectors).

Suppose you have a large mud with a sector size of 4 KB and a snapshot size of 1 GB. Assume that the snapshot size temporarily grows to 2 GB, and then goes back down to 1 GB. The swap map now has 262144 sectors in the free list. Each sector takes up 4 bytes, so the total of wasted memory is 1 MB.

But wait; the swap map is preallocated, so memory usage doesn't actually grow. The only thing that grows is the snapshot, which contains a copy of the used portion of the swap map. The snapshot size grows by 1 MB. That's 0.1 percent of the total size of 1 GB.

[dworkin]

No feedback for 12 days. If you want to pursue this, you can reopen the issue.

[shentino]

Dropped the ball due to being distracted irl.

A large mud is indeed a valid use case, but mud size depends on higher level issues and is probably LPC and usage environment dependent.

Swap table trimming, as you implemented it, genuinely doesn't do much. Free sectors at the end of the map are eliminated from the free list and the swap sectors in the free list are sorted, that's it. One sector that remains allocated at the end will continue to prevent the swap map from shrinking. If that is really so important, then you should remap all used sectors, not just the free list.

This is actually an important point.

For documentation purposes:

The intent behind the original method was to sort the free sectors from front to back, and then trim off the end of the free list starting with the tail.

However, IIRC, keeping the free list sorted front to back had a very useful side effect of encouraging future allocations to be taken from the head of the free list, and the sorting would put the tail of the free list as the last sector to be allocated before extending the swap file.

Runtime fragmentation would, naturally, disturb the strict ordering of the free list. However, if the last used sector were freed and stayed freed until the next snapshot, it's foreseeably likely that it would be included in the next trimming operation.

IIRC, iterations of swap trimming did indeed induce migration of used sectors from the tail of the swap file and bring the holes closer to the tail in preparation for trimming.

In fact, similar logic was used in the course of object table trimming.

Remapping all used sectors would indeed be more effective, however it is presently outside my competence to do this safely.

[dworkin]

A large mud is indeed a valid use case, but mud size depends on higher level issues and is probably LPC and usage environment dependent.

Precisely. It is actually an extreme case, and wasted snapshot space is likely to be far less than 1 megabyte.