avoid atomic op on page free

Hello Andrew et al,

The patch below adds a fast path that avoids the atomic dec and test operation and spinlock acquire/release on page free. This is especially important to the network stack which uses put_page() to free user buffers. Removing these atomic ops helps improve netperf on the P4 from ~8126Mbit/s to ~8199Mbit/s (although that number fluctuates quite a bit with some runs getting 8243Mbit/s). There are probably better workloads to see an improvement from this on, but removing 3 atomics and an irq save/restore is good.

mm/swap.c +0 -0

index cce3dda..d6934cf 100644

Am a bit surprised at those numbers.

Because userspace has to do peculiar things to get its pages taken off the LRU. What exactly was that application doing?

The patch adds slight overhead to the common case while providing improvement to what I suspect is a very uncommon case?

Quoted 2 lines · Benjamin LaHaise

Hello Andrew et al,

Quoted 2 lines

The patch below adds a fast path that avoids the atomic dec and test operation and spinlock acquire/release on page free. This is especially important to the network stack which uses put_page() to free user buffers. Removing these atomic ops helps improve netperf on the P4 from ~8126Mbit/s to ~8199Mbit/s (although that number fluctuates quite a bit with some runs getting 8243Mbit/s). There are probably better workloads to see an improvement from this on, but removing 3 atomics and an irq save/restore is good.

...
Because userspace has to do peculiar things to get its pages taken off the LRU. What exactly was that application doing?

The patch adds slight overhead to the common case while providing improvement to what I suspect is a very uncommon case?

Quoted 4 lines · Andrew Morton

Am a bit surprised at those numbers.

Because userspace has to do peculiar things to get its pages taken off the LRU. What exactly was that application doing?

It's just a simple send() and recv() pair of processes. Networking uses pages for the buffer on user transmits.

Those pages tend to be freed
in irq context on transmit or in the receiver if the traffic is local.

Quoted 2 lines

The patch adds slight overhead to the common case while providing improvement to what I suspect is a very uncommon case?

At least on any modern CPU with branch prediction, the test is essentially free (2 memory reads that pipeline well, iow 1 cycle, maybe 2). The upside is that you get to avoid the atomic (~17 cycles on a P4 with a simple test program, the penalty doubles if there is one other instruction that operates on memory in the loop), disabling interrupts (~20 cycles?, I don't remember) another atomic for the spinlock, another atomic for TestClearPageLRU() and the pushf/popf (expensive as they rely on whatever instruction that might still be in flight to complete and add the penalty for changing irq state). That's at least 70 cycles without including the memory barrier side effects which can cost 100 cycles+. Add in the costs for the cacheline bouncing of the lru_lock and we're talking *expensive*.

So, a 1-2 cycle cost for a case that normally takes from 17 to 100+ cycles? I think that's worth it given the benefits.

Also, I think the common case (page cache read / map) is something that should be done differently, as those atomics really do add up to major pain. Using rcu for page cache reads would be truely wonderful, but that will take some time.

Quoted 2 lines

It's just a simple send() and recv() pair of processes. Networking uses pages for the buffer on user transmits.

You mean non-zero-copy transmits? If they were zero-copy then those pages would still be on the LRU.

Quoted 2 lines

Those pages tend to be freed
in irq context on transmit or in the receiver if the traffic is local.

If it was a non-zero-copy Tx then networking owns that page and can just do free_hot_page() on it and avoid all that stuff in put_page().

Thing is, that case would represent about 1000000th of the number of put_pages()s which get done in the world. IOW: a net loss.

Hello Andrew et al,

The patch below adds a fast path that avoids the atomic dec and test operation and spinlock acquire/release on page free. This is especially important to the network stack which uses put_page() to free user buffers. Removing these atomic ops helps improve netperf on the P4 from ~8126Mbit/s to ~8199Mbit/s (although that number fluctuates quite a bit with some runs getting 8243Mbit/s). There are probably better workloads to see an improvement from this on, but removing 3 atomics and an irq save/restore is good.

-ben

You can't do this because you can't test PageLRU like that.

Have a look in the lkml archives a few months back, where I proposed a way to do this for __free_pages(). You can't do it for put_page.

BTW I have quite a large backlog of patches in -mm which should end up avoiding an atomic or two around these parts.

Quoted 6 lines · Andrew Morton

Am a bit surprised at those numbers.

Because userspace has to do peculiar things to get its pages taken off the LRU. What exactly was that application doing?

It's just a simple send() and recv() pair of processes. Networking uses pages for the buffer on user transmits. Those pages tend to be freed in irq context on transmit or in the receiver if the traffic is local.

Quoted 3 lines

The patch adds slight overhead to the common case while providing improvement to what I suspect is a very uncommon case?

At least on any modern CPU with branch prediction, the test is essentially free (2 memory reads that pipeline well, iow 1 cycle, maybe 2). The upside is that you get to avoid the atomic (~17 cycles on a P4 with a simple test program, the penalty doubles if there is one other instruction that operates on memory in the loop), disabling interrupts (~20 cycles?, I don't remember) another atomic for the spinlock, another atomic for TestClearPageLRU() and the pushf/popf (expensive as they rely on whatever instruction that might still be in flight to complete and add the penalty for changing irq state). That's at least 70 cycles without including the memory barrier side effects which can cost 100 cycles+. Add in the costs for the cacheline bouncing of the lru_lock and we're talking *expensive*.

So, a 1-2 cycle cost for a case that normally takes from 17 to 100+ cycles? I think that's worth it given the benefits.

Also, I think the common case (page cache read / map) is something that should be done differently, as those atomics really do add up to major pain. Using rcu for page cache reads would be truely wonderful, but that will take some time.

I'd say it will turn out to be more trouble than its worth, for the miserly cost
avoiding one atomic_inc, and one atomic_dec_and_test on page-local data that will
be in L1 cache. I'd never turn my nose up at anyone just having a go though :)

Quoted 5 lines · Nick Piggin

You can't do this because you can't test PageLRU like that.

Have a look in the lkml archives a few months back, where I proposed a way to do this for __free_pages(). You can't do it for put_page.

Even if we know that we are the last user of the page (the count is 1)? Who can bump the page's count then?

Quoted 3 lines

BTW I have quite a large backlog of patches in -mm which should end up avoiding an atomic or two around these parts.

That certainly looks like it will help. Not taking the spinlock unconditionally gets rid of quite a bit of the cost.

My patches in -mm avoid the lru_lock and disabling/enabling interrupts if the page is not on lru too, btw.

Quoted 3 lines · Nick Piggin

I'd say it will turn out to be more trouble than its worth, for the miserly cost avoiding one atomic_inc, and one atomic_dec_and_test on page-local data that will be in L1 cache. I'd never turn my nose up at anyone just having a go though :)

The cost is anything but miserly. Consider that every lock instruction is a memory barrier which takes your OoO CPU with lots of instructions in flight to ramp down to just 1 for the time it takes that instruction to execute. That synchronization is what makes the atomic expensive.

In the case of netperf, I ended up with a 2.5Gbit/s (~30%) performance improvement through nothing but microoptimizations. There is method to my madness. ;-)

Nick Piggin wrote on Monday, March 06, 2006 6:05 PM

Quoted 2 lines

My patches in -mm avoid the lru_lock and disabling/enabling interrupts if the page is not on lru too, btw.

Can you put the spin lock/unlock inside TestClearPageLRU()? The difference is subtle though.

- Ken

mm/swap.c renamed from mm/swap.c.orig +8 -6

@@ -210,14 +210,16 @@ int lru_add_drain_all(void)
 void fastcall __page_cache_release(struct page *page)
 {
 	unsigned long flags;
-	struct zone *zone = page_zone(page);
+	struct zone *zone;
 
-	spin_lock_irqsave(&zone->lru_lock, flags);
-	if (TestClearPageLRU(page))
+	if (TestClearPageLRU(page)) {
+		zone = page_zone(page);
+		spin_lock_irqsave(&zone->lru_lock, flags);
 		del_page_from_lru(zone, page);
-	if (page_count(page) != 0)
-		page = NULL;
-	spin_unlock_irqrestore(&zone->lru_lock, flags);
+		if (page_count(page) != 0)
+			page = NULL;
+		spin_unlock_irqrestore(&zone->lru_lock, flags);
+	}
 	if (page)
 		free_hot_page(page);
 }

Those 1-2 cycles are free if you look at how things get scheduled with the execution of the surrounding code. I bet $20 that you can't find a modern CPU where the cost is measurable (meaning something like a P4, Athlon). If this level of cost for the common case is a concern, it's probably worth making atomic_dec_and_test() inline for page_cache_release(). The overhead of the function call and the PageCompound() test is probably more than what we're talking about as you're increasing the cache footprint and actually performing a write to memory.