Poor performance on non-second iteration over int array in JAVA
I have the following function:
public void scanText(char[] T){
int q=0;
for(int i=0;i<T.length;i++){
q = transFunc[preCompRow[q]+T[i]];
if(q==pattern.length){
System.out.println("match found at position: "+(i-pattern.length+2));
}
}
}
This function scans the char Array lookup for matches on a given pattern, which is stored as a state machine. The automata transition function is stored in a variable called transFunc.
I am testing this feature on a text with 8 million characters and using 800,000 templates. The point is, joining the array preCompRow [q] (which is int []) is very slow. Performance is greatly improved if I remove the preCompRow [q] code. I think it might be because in each loop the variable q has a different unclassified value (2, 56, 18, 9 ..).
Is there a better way to access the array in a non-sequential manner?
Thanks in advance!
source to share
One possible explanation is that your code exhibits poor memory performance due to poor locality in memory access patterns.
The role of memory caches in a modern computer is the speed mismatch between processor instruction times (less than 1 ns) and main memory (5 to 10 ns or more). They work best when your code gets the cache the most, when it fetches from memory.
The modern Intel chipset caches memory in blocks of 64 bytes and loads from main memory in batch mode. (This corresponds to a value of 16. int
) The L1 cache on (say) an I7 processor is 2MB.
If your application can access data in a large array (roughly) sequentially, then 7 out of 8 hits will be cache hits. If the access pattern is not sequential, and the "working set" is a large multiple of the cache size, then on every memory access you can lose the cache.
If locality of memory access is the root of yoiur problems then your parameter is limited:
- rework your algorithm to better specify the locality of memory references
- buy equipment with large caches
- (maybe) redesign your algorithm to use GPUs or some other strategy to reduce memory traffic.
Re-coding existing ones to C or C ++ can lead to better performance, but the same memory issues will bite you there as well.
I am not aware of any tools that can be used to measure cache performance in Java applications.
source to share