EGTB sharing - new plan

[Kirill Kryukov]

The internet landscape seems changing. Back in 2005 p2p was the only practical way to share 1.2 TB of data. And it worked beautifully. Now in 2008 while we maintain the basic availability of the files (I know because I share them all), it still takes forever to download them. I was thinking about the way to improve the situation and this idea came.

New idea is based on the following observation: Since recently many hosting companies are offering plans with monthly bandwidth of 15 or 17 TB, for less than $10 a month. This is much cheaper than what I currently pay to keep the files online. My expenses include: cost of the hard disks and the RAID card, cost of electricity used by the disks, by running the machine 24/7 and by air conditioning in summer. Also the disks are noisy. Also, this way I currently upload only about 150 GB a month - 100 times less than a hosting plan would allow to do (theoretically).

So I signed up for one of those plans. 1.5 TB of storage (enough to save complete 6-men Nalimov collection) and 15 TB of monthly bandwidth. It cost me $7 a month. With this plan I theoretically should be able to distribute the whole complete 6-men Nalimov collection to more than 10 people each month. Though it will take time to upload the files to the hosting.

I'm still not sure it will work as well as advertised, so considering it a test run. Of course I can also use the hosting to host other stuff, like normal web-sites.

Some of the hosting companies offering such plans: HostMonster, bluehost, inmotion, FastDomain, Lunarpages, StartLogic, Webhostingpad. I also saw some offers of unlimited storage and unlimited bandwidth, which I somehow don't seem to believe.

If one more person will get such plan, together we will have 30 TB of combined bandwidth. 3 people will provide 45 TB, etc... We can host all files each, or we can divide the files and share only part. Uploading only part of the files will make it faster to upload, and take less space on the hosting server, leaving free space for other projects.

I think that still not many people use 6-men tablebases. This is not because people don't need them, but mainly because there is no easy way of getting them. Many people are not familiar with eMule or p2p, and they are afraid to try new things. Providing the EGTB files as simple HTTP download will make the files available to anyone who can use a browser.

This can be also considered as a test project. When a new useful EGTB format will emerge in future (taking terabytes of space ), we will need an efficient way to distribute the files. May be this way will turn out more efficient than our current p2p sharing.

BTW, I know that some people are already sharing some 6-men files on their web-servers. Your efforts are very valuable and attracted many people to this field. What I am talking now is to take organized approach and get all 6-men Nalimov files shared this way. If no one joins I will try to share all files myself. If someone joins than it will be of course easier and faster.

Any comments or discussion is welcome.

[h.g.muller]

Just to know what is the target to beat:

How long does it typically take to download such a shared 6-men EGTB? I could imagine that at some point computing technology will overtake communication technology, so that recomputing locally becomes faster than downloading. If we have not already reached that point:

An ADSL2 connection has a theoretical maximum download speed of 20 Mbps, i.e. 2.5MB/sec, but in practice one hardly ever does better than half of that (i.e. if you do not live next-doors to a telephone exchange). So 1.25 MB/sec seems a more realistic assumption. Hard-disk transfer rates are now typically 50 MB/sec, i.e. 40 times faster. Now you need to read and write the EGTB for each cycle, so you could do 20 cycles of EGTB generation for one download. And the early cycles might actually be much cheaper than the reading and writing of the finished EGTB, as they will be much better compressible.

What is the typical size of a pawnless 6-men EGTB, and how long does it typically take to download that?

[Kirill Kryukov]

Just to know what is the target to beat:

How long does it typically take to download such a shared 6-men EGTB? I could imagine that at some point computing technology will overtake communication technology, so that recomputing locally becomes faster than downloading. If we have not already reached that point:

An ADSL2 connection has a theoretical maximum download speed of 20 Mbps, i.e. 2.5MB/sec, but in practice one hardly ever does better than half of that (i.e. if you do not live next-doors to a telephone exchange). So 1.25 MB/sec seems a more realistic assumption. Hard-disk transfer rates are now typically 50 MB/sec, i.e. 40 times faster. Now you need to read and write the EGTB for each cycle, so you could do 20 cycles of EGTB generation for one download. And the early cycles might actually be much cheaper than the reading and writing of the finished EGTB, as they will be much better compressible.

What is the typical size of a pawnless 6-men EGTB, and how long does it typically take to download that?

I think communication currently has an edge over computation for EGTB problem. Nalimov tablebases are already compressed when we distribute them. To generate a Nalimov-format tablebase you need much larger space than it occupies when you just download and use it. So when you download a compressed EGTB at 1.25 MB/sec, it may be considered as downloading equivalent uncompressed material at 20 MB/sec or so. (not sure the exact compression rate)

Also downloading a file in a browser should be trivial for anyone. eMule was an obstacle for some people to get the files. Generating may be an obstacle too. Anyway I'll be happy to be proven wrong. If there exists a free generator that can generate EGTB faster than you would download them, I'll be happy. Then this whole initiative will become obsolete and I'll get back 1.2 TB on my hosting.

Nalimov EGTB sizes are listed on this page.

[h.g.muller]

OK, thanks. It seems that a fully unsymmetric one (w.r.t. piece exchange) like KRBNKQ takes about 3GB after compression. That is only about a factor 3 compared to the 8GB an uncompressed 6-men would need. So your 20MB/sec is a bit optimistic at any rate.

But, more importantly, there is no reason why the same compression could not be used during generation. In fact unfinished EGTBs should compress better, because more leading bits of their DTMs are zero, and more DTMs are zero. So I really think this argument plays no role, or even works in favor of generation.

I hope to proof you wrong!

[Kirill Kryukov]

OK, thanks. It seems that a fully unsymmetric one (w.r.t. piece exchange) like KRBNKQ takes about 3GB after compression. That is only about a factor 3 compared to the 8GB an uncompressed 6-men would need. So your 20MB/sec is a bit optimistic at any rate.

But, more importantly, there is no reason why the same compression could not be used during generation. In fact unfinished EGTBs should compress better, because more leading bits of their DTMs are zero, and more DTMs are zero. So I really think this argument plays no role, or even works in favor of generation.

I hope to proof you wrong!

Looking forward to it!

[Codeman]

OK, thanks. It seems that a fully unsymmetric one (w.r.t. piece exchange) like KRBNKQ takes about 3GB after compression. That is only about a factor 3 compared to the 8GB an uncompressed 6-men would need. So your 20MB/sec is a bit optimistic at any rate.

But, more importantly, there is no reason why the same compression could not be used during generation. In fact unfinished EGTBs should compress better, because more leading bits of their DTMs are zero, and more DTMs are zero. So I really think this argument plays no role, or even works in favor of generation.

I hope to proof you wrong!

As far as I know, Nalimov uses some sort of Huffman coding. I don't see any way of using this form of compression during generation. It is only used in the end to compress the finished file. I think you would have to find a different compression algorithm to realize your idea.

Kirill is right!

[h.g.muller]

Why do you think that Huffman coding could not be used on a partially finished EGTB? My algorithm requires, e.g. for building a 2+4 men EGTB, that the EGTB is stored on the HD in chunks of 256KB. I could compress these chunks by any method I want.

For DTC I was considering a kind of run-length encoding scheme for the early passes: in these parses the EGTB is only sparsely filled with non-zero entries (in my encoding 0 = not (yet) won), and the nonzero entries are small numbers. So I considered using 4 bits per entry (in stead of 8 ), where the low numbers (upto the highest number needed in the cycle) would code for themselves, and all other numbers for stretches of zeroes of various lengths. But I am no expert on compression techniques (yet), and perhaps much more efficient schemes do exist. A combination of run-length coding for collapsing groups of zeros into one symbol, until the the frequency of zeros is no longer dominating, followed by a Huffman coding step seems a general, simple and fast scheme.

Anyway, time will tell.

[Codeman]

Well I am no expert on compression either, but I think that encoding during generation might only work for generally drawn endgames. For others it might be difficult, for example if you have a block of 256kb and you find you need 1 more bit at the beginning of the block, you will have to shift all bits in the block 1 to the left. That would be quite time consuming for general won endgames.

This technique I can better imagine for endgames with pawns. Once you have finished generating the white pawn on eight rank positions, you can compress this part of the endgame and continue with the seventh rank.

[h.g.muller]

Well I am no expert on compression either, but I think that encoding during generation might only work for generally drawn endgames. For others it might be difficult, for example if you have a block of 256kb and you find you need 1 more bit at the beginning of the block, you will have to shift all bits in the block 1 to the left. That would be quite time consuming for general won endgames.

But that is not how I plan to do it. The EGTB will be fully decompressed each time it is loaded in RAM (64 or 4096 chunks of 256KB at the time). The building process can then change all bytes through random access in any way it wants. After that, all the 256KB chunks will be recompressed and written back to the disk. The compression itself should be very fast, just a few instructions per byte, so that you could compress perhaps 500 MB/sec.

This technique I can better imagine for endgames with pawns. Once you have finished generating the white pawn on eight rank positions, you can compress this part of the endgame and continue with the seventh rank.

Yes, end-games with Pawns are easy. A 6-men with Pawns can be done entirely in RAM (except for writing the final result, of course). Even without compression. The same holds for 7-men with at least 2 Pawns. It is the 7-men with single Pawn that will be the most difficult. There even the P-slices would have to be build on the HD.

[Codeman]

Ok now I see where you are coming from. Sounds quite nice and I like the idea. Compared to the disk access times the actual compression and decompression wont take very long.

I will think a little more about it too, as I am with my own egtb-generator currently facing the same problem - how to overcome the ram-shortage.

[jkominek]

Computation versus communication: this is a classic systems question. There are (experimental) network systems that factor in both the speed of the communication links and the local CPU. What it decides to do depends. With a fast CPU at hand you compress before sending. If it's slow you just send as is. The equation depends on the payload size too, due to overhead.

I can relay a specific example. To cross-check my work on tbgen2, I set up my spare computer to download the FEG 5-1 files from Kirill's ftp site. The ftp speed from there to here was 32 KB/s. But a couple of files were incomplete, so these I generated. The rate of generation was 10 KB/s on a 1 GHz dual PIII. A top of the line Intel CPU is now 6x faster (single-threaded), so for someone with a deeper wallet than me, computation beats downloading. Until ... I realized I could open 20+ ftp sessions simultaneously and Kirill's server would not kick me off. Aggregate bandwidth ran 400-500 KB/s and that clearly put advantage back in the court of communication.

FEG works with compressed data during generation as far as I can tell, and has a very small memory footprint. Unlike Nalimov's tbgen and my (under development) tbgen2, it never reads from and never saves uncompressed data. So it's more advanced that way.

jk

[jkominek]

By the way, what kind of download speeds can someone expect from emule when starting Nalimov collection for the first time? The peak rates I saw were 120-150 KB/s -- a number limited by the supply of donors, not my DSL link. But that was nearly two years ago. What is it like today? I'd like to imagine it's better now with more people staying online sharing, but I'm not in a position to say.

One thing I have noticed is that I'm uploading to more http:// destinations than to real people. Is the data making its way to central distribution nodes?

john

[Kirill Kryukov]

By the way, what kind of download speeds can someone expect from emule when starting Nalimov collection for the first time? The peak rates I saw were 120-150 KB/s -- a number limited by the supply of donors, not my DSL link. But that was nearly two years ago. What is it like today? I'd like to imagine it's better now with more people staying online sharing, but I'm not in a position to say.

No idea here, someone who downloads the files would have to report.

One thing I have noticed is that I'm uploading to more http:// destinations than to real people. Is the data making its way to central distribution nodes

If you refer to "http://" peers in eMule, then those are just ordinary users who just didn't care to pick a name. Also there are no central distribution nodes in eMule, everyone is supposed to share what he has and what he downloads.

Although new idea of sharing by HTTP can be said to use central distribution nodes. A hosting plan like one I'm trying to use will provide 100 times the bandwidth I have at home, and it is also cheaper than sharing files at home.

[jkominek]

If you refer to "http://" peers in eMule, then those are just ordinary users who just didn't care to pick a name. Also there are no central distribution nodes in eMule.

You mean that when I see a user name of http://emule-project.net it's actually an anonymous user too chicken to put down a nickname? I didn't realize. What with servers advertizing 100M files (or more), I presumed these URLs belonged to an "emule-project.net" server farm, and that they habitually accumulate popular files.

Although new idea of sharing by HTTP can be said to use central distribution nodes. A hosting plan like one I'm trying to use will provide 100 times the bandwidth I have at home, and it is also cheaper than sharing files at home.

Looking forward to hearing about your experience. I took at look at HostMonster and hope you can report back with transfer measurements.

jk

[Kirill Kryukov]

You mean that when I see a user name of http://emule-project.net it's actually an anonymous user too chicken to put down a nickname? I didn't realize.

Yeah exactly.

What with servers advertizing 100M files (or more), I presumed these URLs belonged to an "emule-project.net" server farm, and that they habitually accumulate popular files.

This could be nice. Nothing like this takes place on eMule network, unfortunately. Also if it would, the EGTB files would be among the last considered. (also assuming those servers still have any space left after they "accumulate" all the pron)

Looking forward to hearing about your experience. I took at look at HostMonster and hope you can report back with transfer measurements.

I'll post the link when I set up a distribution web-site there.

[h.g.muller]

The rate of generation was 10 KB/s on a 1 GHz dual PIII.

Well, like I said, HD speeds of 50MB/s are more or less standard now, so if building an EGTB takes 50 cycles, and each cycle a read and a write of the complete EGTB, that makes the generation 100 times slower. So if I will not reach a generation speed of 500KB/sec, I will have done a bad job.
I don't expect the CPU speed to have much impact on the speed, 1GHz would probably be OK, provided the memory isn't too slow. That would become more of an issue if the generation were to be done entirely in RAM.

About the compression:
I did some more thinking about that, and it seems that Huffman coding is indeed a satisfactory way to do it. My internal format uses 1 byte per position, 1 bit (the LSB) for the wtm state, and 7 bits for the btm DTx. (For very long endgames I collapse DTx codes to just a few values when I run out of codes, saving the true DTX in a hardly accessed overflow byte. This has to be done only every 100 cycles or so, and thus doesn't affect performance.)

Early in the building the EGTB will contain mostly zeros (not yet won with both wtm and btm) or 1 (won with wtm), plus a few positions with low DTx values. The latter are initially rare, but the won-with-wtm positions can be upto 30-50% of the positions. (Usually all positions where black has a hanging piece (King included), and white usually covers a significant fraction of the board with his pieces.) So a Hiffman coding scheme, where 0 is indicated by a single bit (0), 1 by 2 bits (10), and all other codes get the prefix 11. If 60% is 0, 30% is 1, and 10% a DTx != 0, distributed over 16 values (DTx 1-8) this would give 0.6*1 + 0.3*2 + 0.1*6 bits = 1.8 bits per position, a compression factor of 4.

Late in the building of a generally-won end-game nearly all positions will be won with wtm, while ~30-40% of the positions are won for white with btm (and thus have DTx != 0). This means the code 1 will be the most frequent, and could deserve the single-bit encoding (0), all other codes getting a '1' prefix. And the DTx itself can probably be limited to 6 bits (not counting possibleoverflows). So the density would be something like 0.6*1+0.4*7 = 3.4 bit per position. That is still a compression factor of 2.35.

[Kirill Kryukov]

Here is the link to my new site: http://kirill-kryukov.com/chess/egtb/files.html

[jkominek]

Here is the link to my new site: http://kirill-kryukov.com/chess/egtb/files.html

I'm doing a test right now, downloading kbbkn.nbb and kbbkn.nbw simultaneously. The typical rate is 95-105 KB/s. I've watched it drop to 60 and go as high as 150. It'll be a couple hours before I have an average download number to report.

Do you know where your new site is hosted?

john

[jkominek]

Well, like I said, HD speeds of 50MB/s are more or less standard now, so if building an EGTB takes 50 cycles, and each cycle a read and a write of the complete EGTB, that makes the generation 100 times slower. So if I will not reach a generation speed of 500KB/sec, I will have done a bad job.

A generator that is streaming IO-bound (as opposed to random access bound) would be a major advance. Supposing you have not done a bad job -- at that rate the entire 6-man tables would take exactly one month to create. Downloading them from emule is a venture on the order of a year.

jk

[h.g.muller]

A generator that is streaming IO-bound (as opposed to random access bound) would be a major advance.

Well, I think this is what my algorithm should be able to deliver:

For a 3+3 men EGTb, say, I would split each cycle in two passes, one pass treating the (retrograde) moves of first white piece plus all black moves, the second pass the moves of the other two white pieces (plus black pieces). So the EGTB on disk would be structured as a 64 x 64 matrix of chunks of 16M positions, the first two white pieces being in the same constellation within every chunk. The row index of this matrix would depend on the position of the first white piece, the column index on that of the second.

The building proces would bring (for each cycle) step through the matrix row by row (first white piece in constant locations within a row) or colums (second in constant locations) of that matrix in RAM. One row or column would occupy 1GB, and all moves treated in the pass would remain within this 1GB working set. Each row or column will have to be brought in memory only once per cycle. By alternating the order of the row-wise and column-wise scans on subsequent cycles, the scans from these subsequent cycles could be combined, and every row or column would be advanced two cycles when it is in memory. So all data has to be read /written nly once per cycle.

The access is not completely sequential: if the matrix is stored by column, the row-wise access would do random access in chuncks of 16MB (or so much less as the compression factor allows). But these chuncks are large enough that the overhead of the 64 seek operations to position the head over the next chunk are completely negligible to the transfer time. (1GB at 50MB/s takes 20 sec, a seek on the order of 10 msec, so 0.6 sec access time.)

[Kirill Kryukov]

Here is the link to my new site: http://kirill-kryukov.com/chess/egtb/files.html

I'm doing a test right now, downloading kbbkn.nbb and kbbkn.nbw simultaneously. The typical rate is 95-105 KB/s. I've watched it drop to 60 and go as high as 150. It'll be a couple hours before I have an average download number to report.

Do you know where your new site is hosted?

john

Thanks for trying, and looking forward to see your resulting speed. It's on bluehost, or do you mean physical location?

[Ray]

I did a quick test and got a good speed. It was fluctuating a lot, but was getting close to the approx 500 kB/s limit of my connection

[Kirill Kryukov]

I did a quick test and got a good speed. It was fluctuating a lot, but was getting close to the approx 500 kB/s limit of my connection

Thanks for checking. Looks like their connection speed is adequate. Much faster than I can upload from home.

[Ray]

Yes, I think it is perfectly fine. I'm not sure what if anything I will actually download. I have here the chessbase "DVD Endgame Turbo 2" which has some 6 men tablebases on it. Presumably they are the most important ones - although this product is quite old now. I have nowhere near enough space for a full set, but a better partial set may be possible over time

Code: Select all

 
Directory of F:\Tablebases\TB6

30/03/2008  13:52    <DIR>          .
30/03/2008  13:52    <DIR>          ..
23/10/2003  01:00       409,022,202 kbppkr.0.nbb.emd
23/10/2003  01:00       367,435,106 kbppkr.0.nbw.emd
23/10/2003  01:00       395,336,141 kbppkr.1.nbb.emd
23/10/2003  01:00       376,393,099 kbppkr.1.nbw.emd
23/10/2003  01:00       385,117,574 kbppkr.2.nbb.emd
23/10/2003  01:00       396,487,077 kbppkr.2.nbw.emd
23/10/2003  01:00       349,416,786 kbppkr.3.nbb.emd
23/10/2003  01:00       396,248,018 kbppkr.3.nbw.emd
23/10/2003  01:00       304,115,210 kbppkr.4.nbb.emd
23/10/2003  01:00       404,021,403 kbppkr.4.nbw.emd
23/10/2003  01:00       300,958,113 kbppkr.5.nbb.emd
23/10/2003  01:00       342,302,299 kbppkr.5.nbw.emd
23/10/2003  01:00       157,025,582 kbppkr.6.nbb.emd
23/10/2003  01:00       524,960,256 knppkr.0.nbb.emd
23/10/2003  01:00       624,717,281 knppkr.0.nbw.emd
23/10/2003  01:00       542,862,739 knppkr.1.nbb.emd
23/10/2003  01:00       634,375,208 knppkr.1.nbw.emd
23/10/2003  01:00       435,589,159 knppkr.2.nbb.emd
23/10/2003  01:00       531,165,780 knppkr.2.nbw.emd
23/10/2003  01:00       110,606,990 knppkr.3.nbb.emd
23/10/2003  01:00       417,284,007 kqqkqq.nbw.emd
23/10/2003  01:00     1,877,096,319 krbknn.nbb.emd
23/10/2003  01:00     2,014,826,249 krbknn.nbw.emd
23/10/2003  01:00       880,049,887 krppkr.0.nbb.emd
23/10/2003  01:00       653,662,668 krppkr.0.nbw.emd
23/10/2003  01:00       862,187,960 krppkr.1.nbb.emd
23/10/2003  01:00       643,882,060 krppkr.1.nbw.emd
23/10/2003  01:00       820,410,149 krppkr.2.nbb.emd
23/10/2003  01:00       581,219,336 krppkr.2.nbw.emd
23/10/2003  01:00       231,093,108 krppkr.3.nbb.emd

30 File(s) 16,969,867,766 bytes
          

[jkominek]

Here is the link to my new site: http://kirill-kryukov.com/chess/egtb/files.html

I'm doing a test right now, downloading kbbkn.nbb and kbbkn.nbw simultaneously. The typical rate is 95-105 KB/s. I've watched it drop to 60 and go as high as 150. It'll be a couple hours before I have an average download number to report.

Do you know where your new site is hosted?

john

Thanks for trying, and looking forward to see your resulting speed. It's on bluehost, or do you mean physical location?

I was wondering about physical location. Ray is in New Zealand?

The two files I selected downloaded at 105 KB/s. Not too shabby.

john