排序1000-2000个元素与许多缓存未命中 [英] Sorting 1000-2000 elements with many cache misses

问题描述

我有一个1000-2000个元素的数组，它们是指向对象的指针。我想保持我的数组排序，显然我想这样做尽可能快。它们由成员排序，并且不连续分配，因此在我访问排序成员时假设缓存未命中。

I have an array of 1000-2000 elements which are pointers to objects. I want to keep my array sorted and obviously I want to do this as quick as possible. They are sorted by a member and not allocated contiguously so assume a cache miss whenever I access the sort-by member.

目前我按需排序，而不是按需排序-add，但是因为缓存未命中和成员访问的非内联，我的快速排序的内循环很慢。

Currently I'm sorting on-demand rather than on-add, but because of the cache misses and [presumably] non-inlining of the member access the inner loop of my quick sort is slow.

我做测试并尝试现在，（并看看实际的瓶颈是什么），但任何人都可以推荐一个好的替代加速这个吗？
我应该做一个插入排序，而不是按需快速排序，或者我应该尝试改变我的模型，使元素接近并减少缓存未命中？
OR，有没有一个排序算法，我没有来到，这是有益的数据，将缓存未命中？

I'm doing tests and trying things now, (and see what the actual bottleneck is) but can anyone recommend a good alternative to speeding this up? Should I do an insert-sort instead of quicksorting on-demand, or should I try and change my model to make the elements contigious and reduce cache misses? OR, is there a sort algorithm I've not come accross which is good for data that is going to cache miss?

编辑：也许我写这个错误:)，我实际上不需要我的数组排序所有的时间（我不是迭代通过他们顺序的任何东西）我只是需要它排序当我做一个二进制斩找到一个匹配的对象，快速排序在当时（当我想搜索）是目前我的瓶颈，因为缓存未命中和跳转（我在我的对象使用<操作符，但我希望内联释放）

Maybe I worded this wrong :), I don't actually need my array sorted all the time (I'm not iterating through them sequentially for anything) I just need it sorted when I'm doing a binary chop to find a matching object, and doing that quicksort at that time (when I want to search) is currently my bottleneck, because of the cache misses and jumps (I'm using a < operator on my object, but I'm hoping that inlines in release)

推荐答案

简单的方法：每插入一个插入排序。因为你的元素不在内存中对齐我猜猜链表。如果是这样，那么你可以将它转换成一个链接列表，跳转到第10个元素，第100个等等。这是类似于下一个建议。

Simple approach: insertion sort on every insert. Since your elements are not aligned in memory I'm guessing linked list. If so, then you could transform it into a linked list with jumps to the 10th element, the 100th and so on. This is kind of similar to the next suggestion.

或者你重组你的容器结构成一个二叉树（或者你喜欢什么树，B，B *黑色，...）和插入元素，如你将它们插入到搜索树。

Or you reorganize your container structure into a binary tree (or what every tree you like, B, B*, red-black, ...) and insert elements like you would insert them into a search tree.

这篇关于排序1000-2000个元素与许多缓存未命中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！