Re: efficient access to "rotational"; new fcntl?
From: Avi Kivity
Date: Sat Sep 19 2009 - 07:40:41 EST
On 09/19/2009 02:30 PM, Arjan van de Ven wrote:
On Sat, 19 Sep 2009 14:11:38 +0300
Avi Kivity<avi@xxxxxxxxxx> wrote:
On 09/19/2009 12:19 PM, Arjan van de Ven wrote:
However, sort *would* benefit, and some UCLA students implemented
that for a term project. Unfortunately, the project is stalled
because the implementation was not efficient enough, and no one
has found the time to improve it since.
parallel sort... call me skeptical. My gut feeling is that you'll
get killed by communication overhead.
(sort seems to be more communication than raw cpu use)
Why? a sort that fits in memory is purely cpu and memory access.
memory access == communication due to cache line bounces....
For a large sort cache line bounces will be negligible. First, memory
size greatly exceeds cache size. Second, every cach eline will be
accessed multiple times.
If you're sorting 2MB, then yes, threads aren't needed.
Instead of O(N log N) you'd get K * O(N/K log N/K) followed by an
O(N) merge. For large N and small K, you get a speedup of roughly K
(since the O(N) merge is dominated by the preceding sort.
doing big-O arithmatic and then add constant divisions/multipliers is
rather.. dangerous ;)
I'm wearing my seat belt.
You actually get K * C1 * O(N/K log N/K) + C2 * O(N)
where C1/C2 is the actual cost of the extra intra-cpu communication.
(and for most sorting, I suspect the communication costs dominate over
CPU cost)
I'd be happy to be proven wrong...
Again, if the dataset is large, only a small fraction of the cache lines
will be on another cpu. The majority will be in main memory.
--
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/