• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Program starts to slow down

 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I have a hash table of objects, of size 2^24 (16.7 million).

I run my program to fill it up, needs to fill around 60% of it.

I also set this "-Xms3840m -Xmx3840m" inside netbeans for the program, it seems to make it run quicker.

While running, the ram is on about 98% (I have 4G, windows 7 home premium 64 bit), and cpu is at 50% (E8600 dual core @4.0 Ghz)

But after half an hour, the ram is the same, but the cpu starts to drop to 10% ish, and it becomes very slowly, potentially taking many hours to finish.


I'm not sure whats causing this, is it cause the table is getting so big, it takes time more time, but I don't get why the cpu % drops.

Any thoughts on how I can do this efficiently?
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
379
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Colin,
CPU does drop when I/O increases because the CPU spends time paging to disk. What are you doing with a HashMap of millions of objects? Is there any way you can do it in batches or in a divide and conquer style?
 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Its not a java HashMap, its just an array of Objects that act as a hash table.

I can't really do it in parts either, but I've got it running now, and hopefully it will finish in a couple of hours.
 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Its gonna take another 6 hours at least.

I think I'll just have to leave it overnight.

Thing is, its going 280 times slower now than when it started. Maybe if I kept reading and writing to a text file, it wouldn't slow it down that way.
But the whole process would be slower. I donno which would be better.
 
Stephan van Hulst
Bartender
Posts: 6320
78
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why would you need a table of that size in the first place? What are you going to do with it?
 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Great question...

Its an opening book for chess engines.
Each table entry was an object containing a 64 bit key for the position, and 2 linkedlists...

My program slowed down even more last night, so I shut it down.
Then today I re-represented the table as a string array, and just crammed all the info into one string.
It only took 20 mins to fill it this time instead of 20+ hours.

Feel free to try the program out here..
Chess Opening Book
 
Stephan van Hulst
Bartender
Posts: 6320
78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, do you need to load it all into memory in one go? Can't you request the data as you need it?
 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not really, as the chess games are scanned, entries in the table have to updated, checked for contents, and also overwritten.

I cant write half the table, then half later, if I did that I'd have to have the first half reloaded back into memory to be able to fill the 2nd half, so might as well do it in one go.

I've done it anyway, and seems to work
 
Adam Kwadratowy
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm having the same issue. Only on Windows 7. I have narrowed it down to a very simple application just writing data to a file. Doesn't matter the name of the file, the disk, anyway the disk is relatively fast and empty (newly formatted, so the fragmentation is none). Always after writing the first almost 2 GB it starts to slow down. It's repeatable with the same pattern. It looks to me like Windows internal scheduling algorithm. (A single output file never exceeds 2 GB of size, just to avoid suspicions it could have something to do with a single file size).
The same application executed on an OSX or Windows XP runs continuously with the same performance. What's that?

JRE 1.7 Update 5, 64bit
Windows 7 Professional 64bit with all available (at the moment of writing this message) updates from MS installed (fresh Win7 installation!).

Code:

 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch, Adam!

Sounds like a paging issue to me. How much physical memory do you have on your Windows 7 box, and how do you configure the -Xms and -Xmx parameters?
 
Adam Kwadratowy
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Martin Vajsar wrote:Welcome to the Ranch, Adam!


Thank you .

Martin Vajsar wrote:
Sounds like a paging issue to me. How much physical memory do you have on your Windows 7 box, and how do you configure the -Xms and -Xmx parameters?


I could imagine a paging issue, if my process would consume enormous amount of memory or at least amount greater than the physical memory available on the machine. But what is the process consuming in this case? Should almost nothing.

Anyway, I made some additional tests. On the OSX and on Windows 7, the same machine (8GB physical memory, leaving -Xms and -Xmx default or setting them to 1024M doesn't show any noticeable difference). I have also increased the buffer size to 32M without noticing any real difference.

OSX (j1.6 u33)
Most of the time getting around 130MB/s. The performance is quite stable and doesn't differ much from iteration to iteration.
Stats:
- real memory size 93M (very slowly growing)
- virtual memory size 2.75G (very slowly growing)
- no shared memory
- private memory size 84M (and stable)
- 10% cpu

Windows 7 (j1.7 u5)
The first 1.9GB written with the speed of 126..225MB/s (most 32MB blocks written closer to 200MB/s).
Then time to time a significant number of consecutive blocks falls down to 30..40MB/s, leading to an average speed of 95MB/s per a 2GB file.
Stats:
- working set 84700k (very slowly growing)
- private working set 79500k (very slowly growing)
- cpu 1 .. 4%
- page faults rapidly growing, around +260/1MB of written data

So ok, you've got me - page faults are there like crazy, but this is normal in Windows caching each open file. In this case the application is accessing always a non-available part of the file, so the page faults come in play. I don't see any difference of the page fault growing speed, whenever the application is writing at higher or at lower speed.

It looks to me like Windows disk caching issue.

Update:
When I force Java to use synchronized file access

then the maximum speed of a block falls down to sth around 110-120MB/s, but at least it stays almost constant. This produces higher average speed. Not much, but still - around 105MB/s.
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, definitely caching. Now that you described it, I realized this is a pattern I've seen before. When I copy a large file using my favorite file manager, it runs blindingly fast until the memory is filled up with the OS cache, then it slows down. When the cache gets empty again, the cycle starts again. Using Process Explorer the peaks and valleys of physical memory usage can be seen.
 
Winston Gutkowski
Bartender
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
colin shuker wrote:Each table entry was an object containing a 64 bit key for the position, and 2 linkedlists...

Hunh??? I'm no great admirer of premature optimization, but a 64-bit key and LinkedLists? Sheesh.

A chess piece position can be encoded in 6 bits (its index) and therefore, if you're not worried about the 33% overhead, a byte. A move can therefore be encoded in 2: (index from, index to - if encoding from the start, the piece is given), so any given chess position can be encoded in (number of moves) * 4 bytes (even less if you do some form of "inverted" Base-64).

Since your program only seems to be concerned with opening sequences, I can't understand why you have all this fabulous data. Create the position and then analyse, or create your Lists while you're re-creating the position, surely - or am I missing something? (It wouldn't be the first time).

Winston
 
Martin Vajsar
Sheriff
Posts: 3752
62
Chrome Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is actually an older zombie being brought up to life, but nevertheless....

The way of encoding positions you've described has the unfortunate property that identical positions obtained by different sequences of moves have different hashes, which defeats the use of hash tables in game engines.....

Anyway, 5 moves is too little for an opening book. Some of the old chess books I have (covered by dust in the bookshelf, I'm afraid) list some variants of the openings way over 20 moves. At these depths, the average size of the key would be certainly higher than 64 bits.

However, I have no idea how opening books are constructed for chess engines. From what Colin has described earlier here, it looks a bit like breadth-first search. I had always thought this kind (ie. memory-intensive) of computations is used for constructing endgame tables.
 
Winston Gutkowski
Bartender
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Martin Vajsar wrote:This is actually an older zombie being brought up to life, but nevertheless....

Oops. Sorry. Always forget that.

However, just to check I went to Wikipedia and...blimey, there's a lot to know! I particularly like the 0x88 method for working out invalid moves.

The way of encoding positions you've described has the unfortunate property that identical positions obtained by different sequences of moves have different hashes, which defeats the use of hash tables in game engines.....

Ah, OK. So you're presumably limited to some kind of bitmap-style of 4 bits per square then (or a Huffman equivalent).

Anyway, 5 moves is too little for an opening book. Some of the old chess books I have (covered by dust in the bookshelf, I'm afraid) list some variants of the openings way over 20 moves. At these depths, the average size of the key would be certainly higher than 64 bits.

20? Sheesh. It's like getting my head around a Go master game; often you haven't got a clue why they made a particular move. It's also an unfortunate fact of Go that, at master level, simply moving first gives you something like a 30% advantage - this on a 20x20 board - and a defeat by more than 4 squares is considered a duffing.

From what Colin has described earlier here, it looks a bit like breadth-first search. I had always thought this kind (ie. memory-intensive) of computations is used for constructing endgame tables.

I have to admit I hadn't got that far. I was simply considering his problem, which seemed to be the sheer amount of data involved. I also worked out from my Wiki browse that my suggestion was a binary form of FEN (and I was right; there are better - ie, more compact - forms).

Winston
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic