Java: производительность HashMap с миллионами элементов по сравнению с поиском if-else для числового диапазона
Нужны советы, если можно. У меня есть метод в моем эмуляторе PlayStation (на основе Java для дипломной работы университета, которая была закончена). Он принимает целочисленный адрес памяти, а затем возвращает байт по этому адресу - перенаправляет чтение в ОЗУ, ПЗУ BIOS, заданный порт ввода-вывода и т. Д. В зависимости от адреса. На данный момент это реализовано с использованием огромного набора случаев if-else, которые проверяют диапазон адресов и соответственно читают из правильного места, возвращая байт.
Это дает производительность около 9% от общего времени выполнения для меня. Я подумал, что смогу улучшить это с помощью таблицы диспетчеризации - по сути, HashMap с автоматически упакованными целочисленными ключами, представляющими адреса памяти, и лямбда-значением для обработки возврата байта в зависимости от адреса. Принимая во внимание, что есть приблизительно 2,6 миллиона различных возможных адресов с учетом карты памяти PS1, это использует намного больше памяти - хорошо с этим.
Меня озадачивает то, что это дает немного худшую производительность, чем набор операторов if-else - около 12% от общего времени выполнения. Есть ли лучший способ сделать то, что я делаю? Я не могу использовать решение массива (адрес в качестве примитивного индекса int и лямбду, хранящуюся в этом индексе), поскольку в адресном пространстве есть пробелы, которые бы не обрабатывались без чрезмерного использования памяти на порядок.
Я ценю любые другие идеи, которые могли бы немного снизить это число - я понимаю, что Java не является отличным языком для эмуляции, но часть моей диссертации была доказательством того, что она будет работать (она работает). Большое спасибо.
С уважением, Фил
РЕДАКТИРОВАТЬ:
Ниже приведен полный код метода readByte (адрес преобразуется в длинный, чтобы можно было сравнивать младшие адреса с старшими при значениях, которые считаются отрицательными для обычного целого):
/**
* 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;
}
4 ответа
Лучший подход зависит от вашей реализации под капотом. Я вижу, что адресное пространство PSX 32-битное, но, как и во многих консольных, зоны зеркально отражаются. Теперь, не видя вашей реальной реализации, это только догадки, но вот некоторые соображения.
Я начну рассматривать эту таблицу
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)
Поэтому для портов ввода / вывода вы мало что можете сделать, поскольку они разделены и должны обрабатываться специально, поэтому мы можем попытаться изучить, как улучшить адресацию всего остального.
Мы видим, что зеркальные области отличаются от 4 самых важных битов. Что означает, что мы можем сделать address &= 0x0FFFFFFF так что мы игнорируем регион и рассматриваем только значимую часть адреса.
Итак, теперь у нас есть 3 вида адресов:
- тот, который начинается в
0x0000000, сопоставленный с основной оперативной памятью - группа, начинающаяся с
0xF000000и заканчивается в0xFC00000(+ bios rom) - порты ввода / вывода в
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 это должно быть разделено на несколько частей. Как вы можете видеть из карты памяти, у нас есть это:
F000000h
F800000h
F801000h
F802000h
FA00000h
FC00000h
Если вы заметили, вы можете увидеть, что первые 4 бита всегда 0xF пока последний 12 биты всегда 0поэтому нам не нужно, чтобы они понимали, куда направить вызов. Это означает, что интересная часть адреса имеет следующую маску 0x0FFF000чтобы мы могли перевести адрес:
address = (address >>> 12) & 0xFFF;
Теперь это только 4096 возможных значений, которые могли бы поместиться в жесткой таблице LUT.
Кажется, реальная проблема вашей текущей реализации не в длинной цепочке if-else, а в их крайне повторяющемся содержании. Это классический пример шаблона, который хорошо подходит для объектно-ориентированного программирования. Вы должны определить общий интерфейс для доступа к сегментам памяти, так что каждый условный блок должен только выглядеть (выбран случайный блок):
...
else if (tempAddress >= 0x1F801104L && tempAddress < 0x1F801108L) {
return timer0.read(tempAddress);
}
...
Существует несколько способов разработки такого класса, но я бы предложил предоставить интерфейс и абстрактный класс, который обрабатывает 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() метод, вы можете найти гуавы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);
}
Это имеет дополнительное преимущество проверки работоспособности вашего адресного пространства, так как ImmutableRangeMap.Builder будет отклонять перекрывающиеся диапазоны. Вы также можете увидеть любые пробелы, построив RangeSet ключей карты и вызов `RangeSet.complement().
HashMap - это O(1) поиск производительности, но это не значит, что она "мгновенная". Внутренне есть много if тесты, вычисления хеш-кода и т. д., кажется, больше, чем происходит с вашими условиями.
Если есть только пара миллионов байтов, я бы просто использовал byte[] и посмотрите - быстрее нет
Вы упомянули автобокс в своем вопросе.
Имейте в виду, что такие преобразования из int в Integer не бесплатны. В этом смысле вы должны убедиться, что слишком много ненужных / нежелательных операций с боксом не происходит.
Для того, чтобы дать вам более подробный ответ, нам нужно будет увидеть часть вашего кода.
Но я согласен с другой обратной связью, которую вы получили: если ваша память помещается в один массив байтов, тогда используйте это; и просто убедитесь, что предоставили разумные интерфейсы вокруг этого.