java - 查找 Java 字节数组的缓存行的开头
问题描述
对于高性能阻塞布隆过滤器,我想将数据对齐到缓存行。(我知道在 C 中做这些技巧更容易,但我想使用 Java。)
我确实有一个解决方案,但我不确定它是否正确,或者是否有更好的方法。我的解决方案尝试使用以下算法查找缓存行的开头:
- 对于每个可能的偏移量 o(0..63;我假设缓存行长度为 64)
- 启动一个从 data[o] 读取并将其写入 data[o + 8] 的线程
- 在主线程中,将 '1' 写入 data[o],然后等到它以 data[o + 8] 结束(所以等待另一个线程)
- 重复一遍
然后,测量这有多快,基本上是 100 万循环(在每个线程中)的增量。我的逻辑是,如果数据在不同的缓存行中,它会更慢。
这是我的代码:
public static void main(String... args) {
for(int i=0; i<20; i++) {
int size = (int) (1000 + Math.random() * 1000);
byte[] data = new byte[size];
int cacheLineOffset = getCacheLineOffset(data);
System.out.println("offset: " + cacheLineOffset);
}
}
private static int getCacheLineOffset(byte[] data) {
for (int i = 0; i < 10; i++) {
int x = tryGetCacheLineOffset(data, i + 3);
if (x != -1) {
return x;
}
}
System.out.println("Cache line start not found");
return 0;
}
private static int tryGetCacheLineOffset(byte[] data, int testCount) {
// assume synchronization between two threads is faster(?)
// if each thread works on the same cache line
int[] counters = new int[64];
int testOffset = 8;
for (int test = 0; test < testCount; test++) {
for (int offset = 0; offset < 64; offset++) {
final int o = offset;
final Semaphore sema = new Semaphore(0);
Thread t = new Thread() {
public void run() {
try {
sema.acquire();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
for (int i = 0; i < 1000000; i++) {
data[o + testOffset] = data[o];
}
}
};
t.start();
sema.release();
data[o] = 1;
int counter = 0;
byte waitfor = 1;
for (int i = 0; i < 1000000; i++) {
byte x = data[o + testOffset];
if (x == waitfor) {
data[o]++;
counter++;
waitfor++;
}
}
try {
t.join();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
counters[offset] += counter;
}
}
Arrays.fill(data, 0, testOffset + 64, (byte) 0);
int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
for (int i = 0; i < 64; i++) {
// average of 3
int avg3 = (counters[(i - 1 + 64) % 64] + counters[i] + counters[(i + 1) % 64]) / 3;
low = Math.min(low, avg3);
high = Math.max(high, avg3);
}
if (low * 1.1 > high) {
// no significant difference between low and high
return -1;
}
int lowCount = 0;
boolean[] isLow = new boolean[64];
for (int i = 0; i < 64; i++) {
if (counters[i] < (low + high) / 2) {
isLow[i] = true;
lowCount++;
}
}
if (lowCount != 8) {
// unclear
return -1;
}
for (int i = 0; i < 64; i++) {
if (isLow[(i - 1 + 64) % 64] && !isLow[i]) {
return i;
}
}
return -1;
}
它打印(示例):
offset: 16
offset: 24
offset: 0
offset: 40
offset: 40
offset: 8
offset: 24
offset: 40
...
所以 Java 中的数组似乎是对齐到 8 个字节的。
解决方案
你知道 GC 可以移动对象......所以你完美对齐的数组可能会在以后错位。
我会尝试ByteBuffer
;我想,直接的对齐很多(到页面边界)。
Unsafe 可以为您提供地址,并且使用 JNI,您可以固定一个数组。
推荐阅读
- python - 如何发送python套接字字节和字符串?
- javascript - React Router 参数无法与 tomcat 一起正常工作
- javascript - checkvalidity 没有检测到错误的值
- javascript - 如何将输入值设置为 redux reducer 文件中的状态?
- julia - 如何获得矩阵形式的 linsolve 解决方案?
- javascript - 响应式更新 vuejs 中的 V-if
- php - php文件下载而不是解析,问题从服务器解决,老用户现在还在继续下载
- swift - 在 Swift 中使用按钮关闭模式视图?
- c# - 我如何满足这些数字舍入标准?
- sql - SQL SERVER:根据两个条件重置运行总计