lib: more scalable list_sort()

+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp should return 0; otherwise, the
+ * return value does not matter.

Quoted 5 lines

+ * The comparison function @cmp must return a negative value if @a
+ * should sort before @b, and a positive value if @a should sort after
+ * @b. If @a and @b are equivalent, and their original relative
+ * ordering is to be preserved, @cmp should return 0; otherwise, the
+ * return value does not matter.

This "otherwise... does not matter" sounds funny and confusing. Either read this as "the return value does not matter if it is neither <0, >0 or ==0" or "the return value does not matter if the function wants it to be ignored". :-)

Just omitting the "otherwise" clause would be clearer.

Olaf

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 552 bytes versus 405 for Mark J. Roberts' code.

Worst case for either implementation is a list length just over a POT, and to roughly the same degree, so here are results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; random initial order.

Quoted 4 lines · Don Mullis

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Quoted 9 lines

Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 552 bytes versus 405 for Mark J. Roberts' code.

Worst case for either implementation is a list length just over a POT, and to roughly the same degree, so here are results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; random initial order.

Could you please add a debugging function which would be compiled-out normally, and which would check that on the output 'list_sort()' gives really sorted list, and number of elements in the list stays the same. You'd call this function before returning from list_sort(). Something like:

#ifdef DEBUG_LIST_SORT
static int list_check(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))

{
   /* Checking */
}

#else
#define list_check(priv, head, cmp) 0
#endif

This will provide more confidence in the algorithm correctness for everyone who modifies 'list_sort()'.

Quoted 32 lines · Artem Bityutskiy

Quoted 4 lines · Don Mullis

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Quoted 9 lines

Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 552 bytes versus 405 for Mark J. Roberts' code.

Worst case for either implementation is a list length just over a POT, and to roughly the same degree, so here are results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; random initial order.

Could you please add a debugging function which would be compiled-out normally, and which would check that on the output 'list_sort()' gives really sorted list, and number of elements in the list stays the same. You'd call this function before returning from list_sort(). Something like:

#ifdef DEBUG_LIST_SORT
static int list_check(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))

{
   /* Checking */
}

#else
#define list_check(priv, head, cmp) 0
#endif

Quoted 2 lines

This will provide more confidence in the algorithm correctness for everyone who modifies 'list_sort()'.

I'd suggest the same method as employed in lib/sort.c - a simple userspace program that verifies correct operation is included in lib/sort.c....

Quoted 19 lines · Dave Chinner

Quoted 18 lines · Artem Bityutskiy

Could you please add a debugging function which would be compiled-out normally, and which would check that on the output 'list_sort()' gives really sorted list, and number of elements in the list stays the same. You'd call this function before returning from list_sort(). Something like:

#ifdef DEBUG_LIST_SORT
static int list_check(void *priv, struct list_head *head,
int (*cmp)(void *priv, struct list_head *a,
struct list_head *b))

{
   /* Checking */
}

#else
#define list_check(priv, head, cmp) 0
#endif

Quoted 6 lines

Quoted 2 lines

This will provide more confidence in the algorithm correctness for everyone who modifies 'list_sort()'.

I'd suggest the same method as employed in lib/sort.c - a simple userspace program that verifies correct operation is included in lib/sort.c....

Yeah, that's also an option.

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Quoted 3 lines · Don Mullis

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

If this can really be called with long lists the function likely needs (optional) need_resched()s Otherwise it could ruin scheduling latencies.

-Andi

Being just a dumb library routine, list_sort() has no idea what context it's been called in, how long a list a particular client could pass in, nor how expensive the client's cmp() callback might be.

The cmp() callback already passes back a client-private pointer. Hanging off of this could be a count of calls, or timing information, maintained by the client. Whenever some threshold is reached, the client's cmp() could do whatever good CPU-sharing citizenship required.

Quoted 9 lines · Don Mullis

Being just a dumb library routine, list_sort() has no idea what context it's been called in, how long a list a particular client could pass in, nor how expensive the client's cmp() callback might be.

The cmp() callback already passes back a client-private pointer. Hanging off of this could be a count of calls, or timing information, maintained by the client. Whenever some threshold is reached, the client's cmp() could do whatever good CPU-sharing citizenship required.

need_resched() does all the timing/thresholding (it checks the reschedule flag set by the timer interrupt). You just have to call it. But preferable not in the inner loop, but in a outer one. It's not hyper-expensive, but it's not free either.

The drawback is that if it's called the context always has to allow sleeping, so it might need to be optional.

Anyways a better fix might be simply to ensure in the caller that lists never get as long that they become a scheduling hazard. But you indicated that ubifs would pass very long lists? Perhaps ubifs (and other calls who might have that problem) simply needs to be fixed.

Quoted 19 lines · Andi Kleen

Quoted 9 lines · Don Mullis

Being just a dumb library routine, list_sort() has no idea what context it's been called in, how long a list a particular client could pass in, nor how expensive the client's cmp() callback might be.

The cmp() callback already passes back a client-private pointer. Hanging off of this could be a count of calls, or timing information, maintained by the client. Whenever some threshold is reached, the client's cmp() could do whatever good CPU-sharing citizenship required.

need_resched() does all the timing/thresholding (it checks the reschedule flag set by the timer interrupt). You just have to call it. But preferable not in the inner loop, but in a outer one. It's not hyper-expensive, but it's not free either.

The drawback is that if it's called the context always has to allow sleeping, so it might need to be optional.

Quoted 5 lines

Anyways a better fix might be simply to ensure in the caller that lists never get as long that they become a scheduling hazard. But you indicated that ubifs would pass very long lists? Perhaps ubifs (and other calls who might have that problem) simply needs to be fixed.

No, they are not very long. A hundred or so I guess, rarely. But we need to check what is really the worst case, but it should not be too many.

Quoted 9 lines · Don Mullis

Being just a dumb library routine, list_sort() has no idea what context it's been called in, how long a list a particular client could pass in, nor how expensive the client's cmp() callback might be.

The cmp() callback already passes back a client-private pointer. Hanging off of this could be a count of calls, or timing information, maintained by the client. Whenever some threshold is reached, the client's cmp() could do whatever good CPU-sharing citizenship required.

need_resched() does all the timing/thresholding (it checks the reschedule flag set by the timer interrupt). You just have to call it. But preferable not in the inner loop, but in a outer one. It's not hyper-expensive, but it's not free either.

The drawback is that if it's called the context always has to allow sleeping, so it might need to be optional.

Anyways a better fix might be simply to ensure in the caller that lists never get as long that they become a scheduling hazard. But you indicated that ubifs would pass very long lists? Perhaps ubifs (and other calls who might have that problem) simply needs to be fixed.

Burning CPU time to save on IO is a very valid tradeoff in filesystem design - burning a few hundred millieseconds of CPU time can result in savcwinge tens of seconds of IO time. Hence passing big long lists to be sorted is not an indication of broken design, it's an indication of understanding CPU time vs IO time tradeoffs during design...

Quoted 6 lines

Burning CPU time to save on IO is a very valid tradeoff in filesystem design - burning a few hundred millieseconds of CPU time can result in savcwinge tens of seconds of IO time. Hence passing big long lists to be sorted is not an indication of broken design, it's an indication of understanding CPU time vs IO time tradeoffs during design...

Burning long CPU time in kernel code without latency breaker code is always a sign of broken design.

Similarly, adding cond_resched() to list_sort means you can stop worrying about the scheduling latency impact of sorting long lists. I fail to see why you're making such a big deal out of this.....

Quoted 3 lines

Similarly, adding cond_resched() to list_sort means you can stop worrying about the scheduling latency impact of sorting long lists. I fail to see why you're making such a big deal out of this.....

It's not easy to add it to a low level library function like list_sort() because you would need to ensure that all callers are allowed to sleep.

Or even if all callers currently allow it future ones might not.

So it would need a new flag or so if needed, completely changing the interface.

Don made IMO a good proposal for the caller to add cond_reshed() in its 'cmp()' callback, if needed. Shouldn't that work fine?

Quoted 3 lines

Similarly, adding cond_resched() to list_sort means you can stop worrying about the scheduling latency impact of sorting long lists. I fail to see why you're making such a big deal out of this.....

It's not easy to add it to a low level library function like list_sort() because you would need to ensure that all callers are allowed to sleep.

Or even if all callers currently allow it future ones might not.

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 552 bytes versus 405 for Mark J. Roberts' code.

Worst case for either implementation is a list length just over a POT, and to roughly the same degree, so here are results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; random initial order.

Quoted 4 lines · Don Mullis

The use of list_sort() by UBIFS looks like it could generate long lists; this alternative implementation scales better, reaching ~3x performance gain as list length approaches the L2 cache size.

Quoted 8 lines

Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 552 bytes versus 405 for Mark J. Roberts' code.

Worst case for either implementation is a list length just over a POT, and to roughly the same degree, so here are results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; random initial order.

This patch breaks UBIFS. I did not have time to dig deeper, but the symptoms is that list_sort() calls the 'cmp()' function with bogus 'struct list_head *a' parameter, which did not exist in the original list.