aspose file tools*
The moose likes Performance and the fly likes Program starts to slow down Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Program starts to slow down" Watch "Program starts to slow down" New topic
Author

Program starts to slow down

colin shuker
Ranch Hand

Joined: Apr 11, 2005
Posts: 744
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
internet detective
Marshal

Joined: May 26, 2003
Posts: 30512
    
150

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?


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
colin shuker
Ranch Hand

Joined: Apr 11, 2005
Posts: 744
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

Joined: Apr 11, 2005
Posts: 744
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

Joined: Sep 20, 2010
Posts: 3646
    
  16

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

Joined: Apr 11, 2005
Posts: 744
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

Joined: Sep 20, 2010
Posts: 3646
    
  16

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

Joined: Apr 11, 2005
Posts: 744
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

Joined: Jun 15, 2012
Posts: 2
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

Joined: Aug 22, 2010
Posts: 3610
    
  60

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

Joined: Jun 15, 2012
Posts: 2
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

Joined: Aug 22, 2010
Posts: 3610
    
  60

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

Joined: Mar 17, 2011
Posts: 7779
    
  21

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


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3610
    
  60

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

Joined: Mar 17, 2011
Posts: 7779
    
  21

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Program starts to slow down