Skip to contentSkip to conversation

Optimise apply_slack() for faster execution

PATCH In review Chinmay V S 1 participant 2 messages Dec 25, 2011 – Dec 27, 2011 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Optimise apply_slack() for faster execution

This patch simplifies the apply_slack() function in the kernel timer subsystem. This is frequently called in mod_timer()/add_timer() and will thus improve the performance of both the functions.

The existing logic used an intermediate-mask and a set of bitwise operations using the mask to round-off the expires_limit variable. This patch discards the intermediate-mask in favour of direct shift-operations.

---
 kernel/timer.c |   22 +++++++++-------------
 1 files changed, 9 insertions(+), 13 deletions(-)
kernel/timer.c +9 -13
index 9c3c62b..3fc1f48 100644
@@ -739,37 +739,33 @@ EXPORT_SYMBOL(mod_timer_pending);
  * Algorithm:
  *   1) calculate the maximum (absolute) time
  *   2) calculate the highest bit where the expires and new max are different
- *   3) use this bit to make a mask
- *   4) use the bitmask to round down the maximum time, so that all last
- *      bits are zeros
+ *   3) use this bit to round down maximum time, so that all last bits are 0
  */
 static inline
 unsigned long apply_slack(struct timer_list *timer, unsigned long expires)
 {
-	unsigned long expires_limit, mask;
+	unsigned long slack = 0;
 	int bit;
 
 	if (timer->slack >= 0) {
-		expires_limit = expires + timer->slack;
+		slack = timer->slack;
 	} else {
 		long delta = expires - jiffies;
 
 		if (delta < 256)
 			return expires;
 
-		expires_limit = expires + delta / 256;
+		slack = delta/256;
 	}
-	mask = expires ^ expires_limit;
-	if (mask == 0)
-		return expires;
 
-	bit = find_last_bit(&mask, BITS_PER_LONG);
+	if (slack == 0)
+		return expires;
 
-	mask = (1 << bit) - 1;
+	bit = find_last_bit(&slack, BITS_PER_LONG);
 
-	expires_limit = expires_limit & ~(mask);
+	expires = (expires >> bit) << bit;
 
-	return expires_limit;
+	return expires;
 }
 
 /**
Signature · 1 line
1.7.0.4

A message that is not in the archive (sent off-list or not yet received): CAK-9PRBFuVQG8cvmry5wtw7d2AM0v+D1eV+YTckox1mS7K6NGw@mail.gmail.com

#2 lore raw

The patch reduces code complexity by:
- Eliminating the need for intermediate expires_limit and mask variables.
- Simplifying the timer-coalescing logic of discarding lesser significant bits.

This leads to smaller mod_timer() and add_timer() subroutines in which apply_slack() is inlined. For example, on a typical x86-build, the patch reduces the size of mod_timer() by 16 instructions.The total mod_timer() function is 173 instructions i.e. the patch makes the function 9% smaller. A typical ARM-build also shows similar savings.

original masking-logic:
shl    %cl,%edx
sub    $0x1,%edx
mov    %edx,-0x10(%ebp)
not    %edx
and    %esi,%edx
mov    %edx,-0x14(%ebp)

patched bitwise logic:
shrl   %cl,-0x14(%ebp)
shll   %cl,-0x14(%ebp)

Enabling function-traces shows us that the mod_timer() and add_timer() functions are called ~1300 times every minute. Hence optimising these functions gives us some significant improvement.

regards
ChinmayVS