Java:具有数百万项的 HashMap 性能与 if-else 搜索数值范围
Java: HashMap performance with millions of items vs if-else searching for numerical range
如果可以的话,正在寻找一些建议。我的 PlayStation 模拟器中有一个方法(Java 基于大学论文,该论文已经完成)。它需要一个整数内存地址,然后 returns 该地址处的字节 - 根据地址将读取重定向到 RAM、BIOS ROM、给定的 I/O 端口等。目前,这是使用大量的 if-else 案例实现的,这些案例检查地址范围并相应地从正确的位置读取,returning 字节。
这对我的整体运行时间造成了大约 9% 的性能损失。我想我可以使用分派 table 来改进这一点——本质上是一个 HashMap,它带有表示内存地址的自动装箱整数键和一个 lambda 值,用于根据地址处理字节的 return。现在请记住,考虑到 PS1 的内存映射,大约有 260 万个不同的可能地址,这会使用更多的内存 - 没关系。
令我困惑的是,这比 if-else 语句包的性能稍差 - 大约占总运行时间的 12%。有没有更好的方法来做我正在做的事情?我不能使用数组解决方案(地址作为原始 int 索引和存储在该索引处的 lambda),因为地址 space 中存在间隙,如果没有一个数量级的过多内存使用,这将无法处理。
我很欣赏任何其他可能使这个数字下降一点的想法 - 我意识到 Java 不是一种很好的仿真语言,但我论文的一部分是证明它会起作用(确实如此)。非常感谢。
此致,
菲尔
编辑:
下面是 readByte 方法的完整代码(地址被转换为 long 以允许将低地址与高地址进行比较,对于普通 int 而言,该值被认为是负值):
/**
* This reads from the correct area depending on the address.
* @param address
* @return
*/
public byte readByte(int address) {
long tempAddress = address & 0xFFFFFFFFL;
byte retVal = 0;
if (tempAddress >= 0L && tempAddress < 0x200000L) { // RAM
retVal = ram[(int)tempAddress];
} else if (tempAddress >= 0x1F000000L && tempAddress < 0x1F800000L) { // Expansion Region 1
// do nothing for now
;
} else if (tempAddress >= 0x1F800000L && tempAddress < 0x1F800400L) { // Scratchpad
// read from data cache scratchpad if enabled
if (scratchpadEnabled()) {
tempAddress -= 0x1F800000L;
retVal = scratchpad[(int)tempAddress];
}
} else if (tempAddress >= 0x1F801000L && tempAddress < 0x1F802000L) { // I/O Ports
if (tempAddress >= 0x1F801000L && tempAddress < 0x1F801004L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion1BaseAddress >>> 24);
break;
case 1:
retVal = (byte)(expansion1BaseAddress >>> 16);
break;
case 2:
retVal = (byte)(expansion1BaseAddress >>> 8);
break;
case 3:
retVal = (byte)expansion1BaseAddress;
break;
}
}
else if (tempAddress >= 0x1F801004L && tempAddress < 0x1F801008L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion2BaseAddress >>> 24);
break;
case 1:
retVal = (byte)(expansion2BaseAddress >>> 16);
break;
case 2:
retVal = (byte)(expansion2BaseAddress >>> 8);
break;
case 3:
retVal = (byte)expansion2BaseAddress;
break;
}
} else if (tempAddress >= 0x1F801008L && tempAddress < 0x1F80100CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion1DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion1DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion1DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion1DelaySize;
break;
}
} else if (tempAddress >= 0x1F80100CL && tempAddress < 0x1F801010L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion3DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion3DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion3DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion3DelaySize;
break;
}
} else if (tempAddress >= 0x1F801010L && tempAddress < 0x1F801014L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(biosRomDelaySize >>> 24);
break;
case 1:
retVal = (byte)(biosRomDelaySize >>> 16);
break;
case 2:
retVal = (byte)(biosRomDelaySize >>> 8);
break;
case 3:
retVal = (byte)biosRomDelaySize;
break;
}
} else if (tempAddress >= 0x1F801014L && tempAddress < 0x1F801018L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(spuDelaySize >>> 24);
break;
case 1:
retVal = (byte)(spuDelaySize >>> 16);
break;
case 2:
retVal = (byte)(spuDelaySize >>> 8);
break;
case 3:
retVal = (byte)spuDelaySize;
break;
}
} else if (tempAddress >= 0x1F801018L && tempAddress < 0x1F80101CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(cdromDelaySize >>> 24);
break;
case 1:
retVal = (byte)(cdromDelaySize >>> 16);
break;
case 2:
retVal = (byte)(cdromDelaySize >>> 8);
break;
case 3:
retVal = (byte)cdromDelaySize;
break;
}
} else if (tempAddress >= 0x1F80101CL && tempAddress < 0x1F801020L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion2DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion2DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion2DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion2DelaySize;
break;
}
} else if (tempAddress >= 0x1F801020L && tempAddress < 0x1F801024L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(commonDelay >>> 24);
break;
case 1:
retVal = (byte)(commonDelay >>> 16);
break;
case 2:
retVal = (byte)(commonDelay >>> 8);
break;
case 3:
retVal = (byte)commonDelay;
break;
}
} else if (tempAddress >= 0x1F801040L && tempAddress < 0x1F801050L) {
// read from ControllerIO object
retVal = cio.readByte((int)tempAddress);
} else if (tempAddress >= 0x1F801060L && tempAddress < 0x1F801064L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(ramSize >>> 24);
break;
case 1:
retVal = (byte)(ramSize >>> 16);
break;
case 2:
retVal = (byte)(ramSize >>> 8);
break;
case 3:
retVal = (byte)ramSize;
break;
}
}
else if (tempAddress >= 0x1F801070L && tempAddress < 0x1F801074L) { // Interrupt Status Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(interruptStatusReg >>> 24);
break;
case 1:
retVal = (byte)(interruptStatusReg >>> 16);
break;
case 2:
retVal = (byte)(interruptStatusReg >>> 8);
break;
case 3:
retVal = (byte)interruptStatusReg;
break;
}
}
else if (tempAddress >= 0x1F801074L && tempAddress < 0x1F801078L) { // Interrupt Mask Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(interruptMaskReg >>> 24);
break;
case 1:
retVal = (byte)(interruptMaskReg >>> 16);
break;
case 2:
retVal = (byte)(interruptMaskReg >>> 8);
break;
case 3:
retVal = (byte)interruptMaskReg;
break;
}
}
else if (tempAddress >= 0x1F801080L && tempAddress < 0x1F801100L) {
retVal = dma.readByte(address);
}
else if (tempAddress >= 0x1F801100L && tempAddress < 0x1F801104L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer0.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801104L && tempAddress < 0x1F801108L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer0.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801108L && tempAddress < 0x1F80110CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer0.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801110L && tempAddress < 0x1F801114L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer1.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801114L && tempAddress < 0x1F801118L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer1.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801118L && tempAddress < 0x1F80111CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer1.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801120L && tempAddress < 0x1F801124L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer2.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801124L && tempAddress < 0x1F801128L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer2.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801128L && tempAddress < 0x1F80112CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer2.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801810L && tempAddress < 0x1F801814L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(gpu.readResponse() >>> 24);
break;
case 1:
retVal = (byte)(gpu.readResponse() >>> 16);
break;
case 2:
retVal = (byte)(gpu.readResponse() >>> 8);
break;
case 3:
retVal = (byte)gpu.readResponse();
break;
}
}
else if (tempAddress >= 0x1F801814L && tempAddress < 0x1F801818L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(gpu.readStatus() >>> 24);
break;
case 1:
retVal = (byte)(gpu.readStatus() >>> 16);
break;
case 2:
retVal = (byte)(gpu.readStatus() >>> 8);
break;
case 3:
retVal = (byte)gpu.readStatus();
break;
}
}
else if (tempAddress >= 0x1F801800L && tempAddress < 0x1F801804L) { // CDROM
switch ((int)tempAddress & 0xF) {
case 0:
retVal = cdrom.read1800();
break;
case 1:
retVal = cdrom.read1801();
break;
case 2:
retVal = cdrom.read1802();
break;
case 3:
retVal = cdrom.read1803();
break;
}
}
else if (tempAddress >= 0x1F801C00L && tempAddress < 0x1F802000L) {
// fake SPU read
retVal = spu.readByte(address);
}
} else if (tempAddress >= 0x1F802000L && tempAddress < 0x1F803000L) { // Expansion Region 2 (I/O Ports)
// read from BIOS post register
if (tempAddress == 0x1F802041L) {
retVal = biosPost;
}
} else if (tempAddress >= 0x1FA00000L && tempAddress < 0x1FC00000L) { // Expansion Region 3 (Multipurpose)
// do nothing for now
;
} else if (tempAddress >= 0x1FC00000L && tempAddress < 0x1FC80000L) { // BIOS ROM
// read from memory mapped BIOS file
tempAddress -= 0x1FC00000L;
retVal = biosBuffer.get((int)tempAddress);
} else if (tempAddress >= 0xFFFE0000L && tempAddress < 0xFFFE0200L) { // I/O Ports (Cache Control)
if (tempAddress >= 0xFFFE0130L && tempAddress < 0xFFFE0134L) { // Cache Control Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(cacheControlReg >>> 24);
break;
case 1:
retVal = (byte)(cacheControlReg >>> 16);
break;
case 2:
retVal = (byte)(cacheControlReg >>> 8);
break;
case 3:
retVal = (byte)cacheControlReg;
break;
}
}
}
return retVal;
}
HashMap 的查找性能为 O(1),但这并不意味着它是 "instantaneous"。内部有很多 if
测试和哈希码计算等,看起来比你的条件要多。
如果只有几百万字节,我会使用 byte[]
并查找 - 没有更快的实现。
您在问题中提到了自动装箱。
请记住,这种从 int 到 Integer 的转换不是免费的。从这个意义上说,您必须确保不会导致发生太多不必要/不需要的装箱操作。
为了给您更详细的答案,我们需要查看您的一些代码。
但我同意您得到的其他反馈:如果您的内存适合单个字节数组,则使用它;并确保为此提供合理的接口。
您当前实施的真正问题似乎不是长 if-else 链,而是它们高度重复的内容。这是一个非常适合面向对象编程的模式的 classic 示例。您应该定义一个用于访问内存段的通用接口,以便每个条件块只需要看起来像(选择一个随机块):
...
else if (tempAddress >= 0x1F801104L && tempAddress < 0x1F801108L) {
return timer0.read(tempAddress);
}
...
有多种方法可以设计这样的 class,但我建议提供一个接口和一个抽象 class 来处理 switch
行为:
interface Location {
byte read(long address);
}
abstract class IntWordLocation implements Location {
@Override
final byte read(long address) {
int value = readInt(address & 0xfffffffd); // clear lower two bits;
int shift = 3 - (int) (address & 0x3);
for (int i = 0; i < shift; i++) { // replaces switch statement
value = value >>> 8;
}
return (byte) value;
}
abstract protected int readInt(long int);
}
并且您可以根据需要添加其他 Location
实现。现在我们已经将读取特定内存段(Location
现在负责)与查找地址代表的段(您的 if-else 块)分离了,现在您的 readByte()
方法应该简单多了。
如果您想进一步清理 readByte()
方法,您可能会发现 Guava's RangeMap
很有用 - 它允许您有效地表示值范围的映射,这意味着您可以为每个值存储一个条目内存位置,而不是尝试单独映射每个地址。该地图将只包含几个条目,而不是非常大。
例如:
RangeMap<Long, Location> addressRanges =
new ImmutableRangeMap.Builder<Integer, Location>()
.put(Range.closedOpen(0L, 0x200000L), ramLocation)
.put(Range.closedOpen(0x1F000000L, 0x1F800000L), NO_OP_LOCATION)
.put(Range.closedOpen(0x1F800000L, 0x1F800400L), scratchpadLocation)
// ...
.build();
那么您的 readByte()
方法就变成了:
public byte readByte(int address) {
return addressRanges.get(address).read(address);
}
这有一个额外的好处,可以检查您的地址 -space,因为 ImmutableRangeMap.Builder
将拒绝重叠范围。您还可以通过构造地图键的 RangeSet
并调用 `RangeSet.complement().
来查看任何间隙
最佳方法取决于您在幕后的实施。我看到 PSX 的地址 space 是 32 位的,但与许多控制台一样,区域是镜像的。现在没有看到您的实际实现,这只是猜测,但这里有一些注意事项。
我会开始考虑这个table
KUSEG KSEG0 KSEG1
00000000h 80000000h A0000000h 2048K Main RAM (first 64K reserved for BIOS)
1F000000h 9F000000h BF000000h 8192K Expansion Region 1 (ROM/RAM)
1F800000h 9F800000h -- 1K Scratchpad (D-Cache used as Fast RAM)
1F801000h 9F801000h BF801000h 8K I/O Ports
1F802000h 9F802000h BF802000h 8K Expansion Region 2 (I/O Ports)
1FA00000h 9FA00000h BFA00000h 2048K Expansion Region 3 (whatever purpose)
1FC00000h 9FC00000h BFC00000h 512K BIOS ROM (Kernel) (4096K max)
FFFE0000h (KSEG2) 0.5K I/O Ports (Cache Control)
因此,对于 I/O 端口,您无能为力,因为它们是分开的,必须专门处理,我们可以尝试研究如何改进其他所有内容的寻址。
我们可以看到镜像区域与 4 个最相关的位不同。这意味着我们可以 address &= 0x0FFFFFFF
忽略区域并只考虑地址的有效部分。
所以现在我们有 3 种地址:
- 从
0x0000000
开始的映射到主 RAM
- 组开始于
0xF000000
结束于 0xFC00000
(+ bios rom)
- I/O 端口位于
0xFFFF0000
这可能会导致您同时使用 if/else 和缓存的混合方法,例如:
byte readMemory(int address)
{
if ((address & 0xFF000000) == 0xFF000000)
return ioPorts.read(address);
// remove most significative nibble, we don't need it
address &= 0x0FFFFFFF;
// 0xF000000 zone
// according to bios rom size you could need a different kind of comparison since it may wrap over 0xFFFFFFF
if ((address & 0xF000000) == 0xF000000)
{
// now your address space is just from 0xF000000 to 0xFC00000 + size of BIOS ROM (4mb max?)
}
else
{
// we don't know if you map bios together with ram or separately
return mainRam.readMemory(address);
}
}
现在我们有 0xF000000
和 0xFC000000
之间的地址 space,必须拆分成多个部分。正如您从内存映射中看到的那样:
F000000h
F800000h
F801000h
F802000h
FA00000h
FC00000h
如果您注意到,您会发现前 4 位始终是 0xF
,而最后 12
位始终是 0
,因此我们不需要它们来了解要发送到哪里电话。这意味着地址的有趣部分具有以下掩码 0x0FFF000
,因此我们可以翻译地址:
address = (address >>> 12) & 0xFFF;
现在这些只有 4096 个可能的值可以适合一个紧凑的 LUT table。
如果可以的话,正在寻找一些建议。我的 PlayStation 模拟器中有一个方法(Java 基于大学论文,该论文已经完成)。它需要一个整数内存地址,然后 returns 该地址处的字节 - 根据地址将读取重定向到 RAM、BIOS ROM、给定的 I/O 端口等。目前,这是使用大量的 if-else 案例实现的,这些案例检查地址范围并相应地从正确的位置读取,returning 字节。
这对我的整体运行时间造成了大约 9% 的性能损失。我想我可以使用分派 table 来改进这一点——本质上是一个 HashMap,它带有表示内存地址的自动装箱整数键和一个 lambda 值,用于根据地址处理字节的 return。现在请记住,考虑到 PS1 的内存映射,大约有 260 万个不同的可能地址,这会使用更多的内存 - 没关系。
令我困惑的是,这比 if-else 语句包的性能稍差 - 大约占总运行时间的 12%。有没有更好的方法来做我正在做的事情?我不能使用数组解决方案(地址作为原始 int 索引和存储在该索引处的 lambda),因为地址 space 中存在间隙,如果没有一个数量级的过多内存使用,这将无法处理。
我很欣赏任何其他可能使这个数字下降一点的想法 - 我意识到 Java 不是一种很好的仿真语言,但我论文的一部分是证明它会起作用(确实如此)。非常感谢。
此致, 菲尔
编辑:
下面是 readByte 方法的完整代码(地址被转换为 long 以允许将低地址与高地址进行比较,对于普通 int 而言,该值被认为是负值):
/**
* This reads from the correct area depending on the address.
* @param address
* @return
*/
public byte readByte(int address) {
long tempAddress = address & 0xFFFFFFFFL;
byte retVal = 0;
if (tempAddress >= 0L && tempAddress < 0x200000L) { // RAM
retVal = ram[(int)tempAddress];
} else if (tempAddress >= 0x1F000000L && tempAddress < 0x1F800000L) { // Expansion Region 1
// do nothing for now
;
} else if (tempAddress >= 0x1F800000L && tempAddress < 0x1F800400L) { // Scratchpad
// read from data cache scratchpad if enabled
if (scratchpadEnabled()) {
tempAddress -= 0x1F800000L;
retVal = scratchpad[(int)tempAddress];
}
} else if (tempAddress >= 0x1F801000L && tempAddress < 0x1F802000L) { // I/O Ports
if (tempAddress >= 0x1F801000L && tempAddress < 0x1F801004L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion1BaseAddress >>> 24);
break;
case 1:
retVal = (byte)(expansion1BaseAddress >>> 16);
break;
case 2:
retVal = (byte)(expansion1BaseAddress >>> 8);
break;
case 3:
retVal = (byte)expansion1BaseAddress;
break;
}
}
else if (tempAddress >= 0x1F801004L && tempAddress < 0x1F801008L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion2BaseAddress >>> 24);
break;
case 1:
retVal = (byte)(expansion2BaseAddress >>> 16);
break;
case 2:
retVal = (byte)(expansion2BaseAddress >>> 8);
break;
case 3:
retVal = (byte)expansion2BaseAddress;
break;
}
} else if (tempAddress >= 0x1F801008L && tempAddress < 0x1F80100CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion1DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion1DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion1DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion1DelaySize;
break;
}
} else if (tempAddress >= 0x1F80100CL && tempAddress < 0x1F801010L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion3DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion3DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion3DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion3DelaySize;
break;
}
} else if (tempAddress >= 0x1F801010L && tempAddress < 0x1F801014L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(biosRomDelaySize >>> 24);
break;
case 1:
retVal = (byte)(biosRomDelaySize >>> 16);
break;
case 2:
retVal = (byte)(biosRomDelaySize >>> 8);
break;
case 3:
retVal = (byte)biosRomDelaySize;
break;
}
} else if (tempAddress >= 0x1F801014L && tempAddress < 0x1F801018L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(spuDelaySize >>> 24);
break;
case 1:
retVal = (byte)(spuDelaySize >>> 16);
break;
case 2:
retVal = (byte)(spuDelaySize >>> 8);
break;
case 3:
retVal = (byte)spuDelaySize;
break;
}
} else if (tempAddress >= 0x1F801018L && tempAddress < 0x1F80101CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(cdromDelaySize >>> 24);
break;
case 1:
retVal = (byte)(cdromDelaySize >>> 16);
break;
case 2:
retVal = (byte)(cdromDelaySize >>> 8);
break;
case 3:
retVal = (byte)cdromDelaySize;
break;
}
} else if (tempAddress >= 0x1F80101CL && tempAddress < 0x1F801020L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(expansion2DelaySize >>> 24);
break;
case 1:
retVal = (byte)(expansion2DelaySize >>> 16);
break;
case 2:
retVal = (byte)(expansion2DelaySize >>> 8);
break;
case 3:
retVal = (byte)expansion2DelaySize;
break;
}
} else if (tempAddress >= 0x1F801020L && tempAddress < 0x1F801024L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(commonDelay >>> 24);
break;
case 1:
retVal = (byte)(commonDelay >>> 16);
break;
case 2:
retVal = (byte)(commonDelay >>> 8);
break;
case 3:
retVal = (byte)commonDelay;
break;
}
} else if (tempAddress >= 0x1F801040L && tempAddress < 0x1F801050L) {
// read from ControllerIO object
retVal = cio.readByte((int)tempAddress);
} else if (tempAddress >= 0x1F801060L && tempAddress < 0x1F801064L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(ramSize >>> 24);
break;
case 1:
retVal = (byte)(ramSize >>> 16);
break;
case 2:
retVal = (byte)(ramSize >>> 8);
break;
case 3:
retVal = (byte)ramSize;
break;
}
}
else if (tempAddress >= 0x1F801070L && tempAddress < 0x1F801074L) { // Interrupt Status Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(interruptStatusReg >>> 24);
break;
case 1:
retVal = (byte)(interruptStatusReg >>> 16);
break;
case 2:
retVal = (byte)(interruptStatusReg >>> 8);
break;
case 3:
retVal = (byte)interruptStatusReg;
break;
}
}
else if (tempAddress >= 0x1F801074L && tempAddress < 0x1F801078L) { // Interrupt Mask Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(interruptMaskReg >>> 24);
break;
case 1:
retVal = (byte)(interruptMaskReg >>> 16);
break;
case 2:
retVal = (byte)(interruptMaskReg >>> 8);
break;
case 3:
retVal = (byte)interruptMaskReg;
break;
}
}
else if (tempAddress >= 0x1F801080L && tempAddress < 0x1F801100L) {
retVal = dma.readByte(address);
}
else if (tempAddress >= 0x1F801100L && tempAddress < 0x1F801104L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer0.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801104L && tempAddress < 0x1F801108L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer0.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801108L && tempAddress < 0x1F80110CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer0.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer0.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer0.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer0.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801110L && tempAddress < 0x1F801114L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer1.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801114L && tempAddress < 0x1F801118L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer1.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801118L && tempAddress < 0x1F80111CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer1.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer1.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer1.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer1.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801120L && tempAddress < 0x1F801124L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterValueRead() >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterValueRead() >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterValueRead() >>> 8);
break;
case 3:
retVal = (byte)timer2.counterValueRead();
break;
}
}
else if (tempAddress >= 0x1F801124L && tempAddress < 0x1F801128L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterModeRead(false) >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterModeRead(false) >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterModeRead(false) >>> 8);
break;
case 3:
retVal = (byte)timer2.counterModeRead(false);
break;
}
}
else if (tempAddress >= 0x1F801128L && tempAddress < 0x1F80112CL) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(timer2.counterTargetRead() >>> 24);
break;
case 1:
retVal = (byte)(timer2.counterTargetRead() >>> 16);
break;
case 2:
retVal = (byte)(timer2.counterTargetRead() >>> 8);
break;
case 3:
retVal = (byte)timer2.counterTargetRead();
break;
}
}
else if (tempAddress >= 0x1F801810L && tempAddress < 0x1F801814L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(gpu.readResponse() >>> 24);
break;
case 1:
retVal = (byte)(gpu.readResponse() >>> 16);
break;
case 2:
retVal = (byte)(gpu.readResponse() >>> 8);
break;
case 3:
retVal = (byte)gpu.readResponse();
break;
}
}
else if (tempAddress >= 0x1F801814L && tempAddress < 0x1F801818L) {
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(gpu.readStatus() >>> 24);
break;
case 1:
retVal = (byte)(gpu.readStatus() >>> 16);
break;
case 2:
retVal = (byte)(gpu.readStatus() >>> 8);
break;
case 3:
retVal = (byte)gpu.readStatus();
break;
}
}
else if (tempAddress >= 0x1F801800L && tempAddress < 0x1F801804L) { // CDROM
switch ((int)tempAddress & 0xF) {
case 0:
retVal = cdrom.read1800();
break;
case 1:
retVal = cdrom.read1801();
break;
case 2:
retVal = cdrom.read1802();
break;
case 3:
retVal = cdrom.read1803();
break;
}
}
else if (tempAddress >= 0x1F801C00L && tempAddress < 0x1F802000L) {
// fake SPU read
retVal = spu.readByte(address);
}
} else if (tempAddress >= 0x1F802000L && tempAddress < 0x1F803000L) { // Expansion Region 2 (I/O Ports)
// read from BIOS post register
if (tempAddress == 0x1F802041L) {
retVal = biosPost;
}
} else if (tempAddress >= 0x1FA00000L && tempAddress < 0x1FC00000L) { // Expansion Region 3 (Multipurpose)
// do nothing for now
;
} else if (tempAddress >= 0x1FC00000L && tempAddress < 0x1FC80000L) { // BIOS ROM
// read from memory mapped BIOS file
tempAddress -= 0x1FC00000L;
retVal = biosBuffer.get((int)tempAddress);
} else if (tempAddress >= 0xFFFE0000L && tempAddress < 0xFFFE0200L) { // I/O Ports (Cache Control)
if (tempAddress >= 0xFFFE0130L && tempAddress < 0xFFFE0134L) { // Cache Control Register
int shift = (int)(tempAddress & 0x3L);
switch (shift) {
case 0:
retVal = (byte)(cacheControlReg >>> 24);
break;
case 1:
retVal = (byte)(cacheControlReg >>> 16);
break;
case 2:
retVal = (byte)(cacheControlReg >>> 8);
break;
case 3:
retVal = (byte)cacheControlReg;
break;
}
}
}
return retVal;
}
HashMap 的查找性能为 O(1),但这并不意味着它是 "instantaneous"。内部有很多 if
测试和哈希码计算等,看起来比你的条件要多。
如果只有几百万字节,我会使用 byte[]
并查找 - 没有更快的实现。
您在问题中提到了自动装箱。
请记住,这种从 int 到 Integer 的转换不是免费的。从这个意义上说,您必须确保不会导致发生太多不必要/不需要的装箱操作。
为了给您更详细的答案,我们需要查看您的一些代码。
但我同意您得到的其他反馈:如果您的内存适合单个字节数组,则使用它;并确保为此提供合理的接口。
您当前实施的真正问题似乎不是长 if-else 链,而是它们高度重复的内容。这是一个非常适合面向对象编程的模式的 classic 示例。您应该定义一个用于访问内存段的通用接口,以便每个条件块只需要看起来像(选择一个随机块):
...
else if (tempAddress >= 0x1F801104L && tempAddress < 0x1F801108L) {
return timer0.read(tempAddress);
}
...
有多种方法可以设计这样的 class,但我建议提供一个接口和一个抽象 class 来处理 switch
行为:
interface Location {
byte read(long address);
}
abstract class IntWordLocation implements Location {
@Override
final byte read(long address) {
int value = readInt(address & 0xfffffffd); // clear lower two bits;
int shift = 3 - (int) (address & 0x3);
for (int i = 0; i < shift; i++) { // replaces switch statement
value = value >>> 8;
}
return (byte) value;
}
abstract protected int readInt(long int);
}
并且您可以根据需要添加其他 Location
实现。现在我们已经将读取特定内存段(Location
现在负责)与查找地址代表的段(您的 if-else 块)分离了,现在您的 readByte()
方法应该简单多了。
如果您想进一步清理 readByte()
方法,您可能会发现 Guava's RangeMap
很有用 - 它允许您有效地表示值范围的映射,这意味着您可以为每个值存储一个条目内存位置,而不是尝试单独映射每个地址。该地图将只包含几个条目,而不是非常大。
例如:
RangeMap<Long, Location> addressRanges =
new ImmutableRangeMap.Builder<Integer, Location>()
.put(Range.closedOpen(0L, 0x200000L), ramLocation)
.put(Range.closedOpen(0x1F000000L, 0x1F800000L), NO_OP_LOCATION)
.put(Range.closedOpen(0x1F800000L, 0x1F800400L), scratchpadLocation)
// ...
.build();
那么您的 readByte()
方法就变成了:
public byte readByte(int address) {
return addressRanges.get(address).read(address);
}
这有一个额外的好处,可以检查您的地址 -space,因为 ImmutableRangeMap.Builder
将拒绝重叠范围。您还可以通过构造地图键的 RangeSet
并调用 `RangeSet.complement().
最佳方法取决于您在幕后的实施。我看到 PSX 的地址 space 是 32 位的,但与许多控制台一样,区域是镜像的。现在没有看到您的实际实现,这只是猜测,但这里有一些注意事项。
我会开始考虑这个table
KUSEG KSEG0 KSEG1
00000000h 80000000h A0000000h 2048K Main RAM (first 64K reserved for BIOS)
1F000000h 9F000000h BF000000h 8192K Expansion Region 1 (ROM/RAM)
1F800000h 9F800000h -- 1K Scratchpad (D-Cache used as Fast RAM)
1F801000h 9F801000h BF801000h 8K I/O Ports
1F802000h 9F802000h BF802000h 8K Expansion Region 2 (I/O Ports)
1FA00000h 9FA00000h BFA00000h 2048K Expansion Region 3 (whatever purpose)
1FC00000h 9FC00000h BFC00000h 512K BIOS ROM (Kernel) (4096K max)
FFFE0000h (KSEG2) 0.5K I/O Ports (Cache Control)
因此,对于 I/O 端口,您无能为力,因为它们是分开的,必须专门处理,我们可以尝试研究如何改进其他所有内容的寻址。
我们可以看到镜像区域与 4 个最相关的位不同。这意味着我们可以 address &= 0x0FFFFFFF
忽略区域并只考虑地址的有效部分。
所以现在我们有 3 种地址:
- 从
0x0000000
开始的映射到主 RAM - 组开始于
0xF000000
结束于0xFC00000
(+ bios rom) - I/O 端口位于
0xFFFF0000
这可能会导致您同时使用 if/else 和缓存的混合方法,例如:
byte readMemory(int address)
{
if ((address & 0xFF000000) == 0xFF000000)
return ioPorts.read(address);
// remove most significative nibble, we don't need it
address &= 0x0FFFFFFF;
// 0xF000000 zone
// according to bios rom size you could need a different kind of comparison since it may wrap over 0xFFFFFFF
if ((address & 0xF000000) == 0xF000000)
{
// now your address space is just from 0xF000000 to 0xFC00000 + size of BIOS ROM (4mb max?)
}
else
{
// we don't know if you map bios together with ram or separately
return mainRam.readMemory(address);
}
}
现在我们有 0xF000000
和 0xFC000000
之间的地址 space,必须拆分成多个部分。正如您从内存映射中看到的那样:
F000000h
F800000h
F801000h
F802000h
FA00000h
FC00000h
如果您注意到,您会发现前 4 位始终是 0xF
,而最后 12
位始终是 0
,因此我们不需要它们来了解要发送到哪里电话。这意味着地址的有趣部分具有以下掩码 0x0FFF000
,因此我们可以翻译地址:
address = (address >>> 12) & 0xFFF;
现在这些只有 4096 个可能的值可以适合一个紧凑的 LUT table。