Improving bigint disk write performance

Question

I work with really large bigint numbers, and I need to write them to disk and read them later, because they will not all fit into memory at a time.

The current implementation of Chapel first converts bigint to string , and then writes that string to disk [1]. This takes a lot of time for large integers.

 var outputFile = open("outputPath", iomode.cwr); var writer = outputFile.writer(); writer.write(reallyLargeBigint); writer.close(); outputFile.close(); 

Is there a way to use GMP mpz_out_raw() / mpz_inp_raw() [2] or mpz_export() / mpz_import() [3] or another similar way to dump bigint bytes to disk directly without going to the line beforehand and then read the bytes back to the object bigint ?

Will this work for the bigint array as bigint ?

How can I add such functionality to the standard Chapel library if it is not possible in the current state?

[1] https://github.com/chapel-lang/chapel/blob/master/modules/standard/BigInteger.chpl#L346

[2] https://gmplib.org/manual/I_002fO-of-Integers.html

[3] https://gmplib.org/manual/Integer-Import-and-Export.html

Answer 1

The functions you specify are not directly available in any Chapel modules, but you can write extern procs and extern types for direct access to GMP functions.

First, we should be able to work with C files, so we declare some procedures and types for them:

 extern type FILE; extern type FILEptr = c_ptr(FILE); extern proc fopen(filename: c_string, mode: c_string): FILEptr; extern proc fclose(fp: FILEptr); 

Then we can declare the GMP functions that we need:

 extern proc mpz_out_raw(stream: FILEptr, const op: mpz_t): size_t; extern proc mpz_inp_raw(ref rop: mpz_t, stream: FILEptr): size_t; 

Now we can use them to write the bigint value:

 use BigInteger; var res: bigint; res.fac(100); // Compute 100! writeln("Writing the number: ", res); var f = fopen("gmp_outfile", "w"); mpz_out_raw(f, res.mpz); fclose(f); 

And read it back from the file:

 var readIt: bigint; f = fopen("gmp_outfile", "r"); mpz_inp_raw(readIt.mpz, f); fclose(f); writeln("Read the number:", readIt); 

For arrays of bigint values bigint just bigint over them to write or read them:

 // initialize the array var A: [1..10] bigint; for i in 1..10 do A[i].fac(i); // write the array to a file f = fopen("gmp_outfile", "w"); for i in 1..10 do mpz_out_raw(f, A[i].mpz); fclose(f); // read the array back in from the file var B: [1..10] bigint; f = fopen("gmp_outfile", "r"); for i in 1..10 do mpz_inp_raw(B[i].mpz, f); fclose(f); 

Answer 2

Prologue:
size data is a static attribute, but the stream is always our worst enemy.

"Can such functionality be added to the standard Chapel library?"

With the current price of adding a few units, tens or even many hundreds of [TB] -s of RAM capacity, the IMHO problem will never be resolved with any kind of language extension in the outline above.

---

Why not? Due to exploding costs:

If someone spends just a few moments with the facts, the next delay card appears on a blank sheet of paper. Although the corresponding numbers may vary slightly, the message is in order of magnitude and in the chain of dependencies of the thought process:

  ________________________________________________________________________________________ / / / ________________________________________________________ / / / / / / / xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx / / / / / / / / / / / SOMEWHAT / PRETTY / PROHIBITIVELY / / / / CHEAPEST / CHEAP / EXPENSIVE / EXPENSIVE / / / / EVER / ZONE / ZONE / ZONE / / / /___________________/. . . . . / _ _ _ _ _ _ _ _/ ! ! ! ! ! ! ! !/ / /_______________________ / / / / / / / / / in-CACHE / in-RAM / CONVERT / STORE / RE-READ / CONVERT / in-RAM / in-CACHE / in-CPU-uop / ~ + 5 [ns] | | | | | | | | + 5 [ns] | | | | | | | | | | | | | | | | | | ~ +300 [ns/kB] | | | | | | | | +300 [ns/kB] | | | | | | | | | | | | | | | | | |+VOLUME [ GB] | | | | | | | | x 100.000[ns/GB] | | | | | | | | | | | | | | | | | |+1 | | | | | | | | | x 15.000.000[ns] | | | | | | | |+VOLUME [ GB] | | | | | | | | x 3.580.000.000[ns/GB] | | | | | | | | | | | | | | | | | |+1 FIND | | | | | | | | | x 15.000.000[ns] | | | | | | | |+1 DATA | | | | | | | | | x 15.000.000[ns] | | | | | | | |+VOLUME [ GB] | | | | | | | | x 3.580.000.000[ns/GB] | | | | | | | | | | | | | | | | | |+VOLUME [ GB] | | | | | | | | x 100.000[ns/GB] | | | | | | | | | | | | | | | | | | ~ +300 [ns/kB] | | | | | | | | +300 [ns/kB] | | | | | | | | | | | | | | | | | | ~ + 5 [ns] | | | | | | | | + 5 [ns] | | | | | | | | | | | | | | | | | | ~ + 0.3 [ns/uop] | | | | | | | | + 2.0 [ns/uop] 

---

Last but not least, calculate such step effects at << 1.0 speedup

Given the original processing, it took XYZ [ns] ,
"modified" processing will take:

  XYZ [ns] : the PURPOSE + ( VOL [GB] * 300.000.000 [ns/GB] ) : + MEM/CONVERT + ( VOL [GB] * 100.000 [ns/GB] ) : + CPU/CONVERT + 15.000.000 [ns] : + fileIO SEEK + ( VOL [GB] * 3.580.000.000 [ns/GB] ) : + fileIO STORE + 15.000.000 [ns] : + fileIO SEEK / FAT + 15.000.000 [ns] : + fileIO SEEK / DATA + ( VOL [GB] * 3.580.000.000 [ns/GB] ) : + fileIO RE-READ + ( VOL [GB] * 100.000 [ns/GB] ) : + CPU/CONVERT + ( VOL [GB] * 300.000.000 [ns/GB] ) : + MEM/CONVERT _______________________________________________ 45.000.XYZ [ns] + 7.660.200.000 [ns/GB] * VOL [GB] 

so that such adverse performance will be damaged (as Amdahl's law shows):

  1 S = ------------------------------------------------------------ << 1.00 1 + ( 45.000.XYZ [ns] + 7.660.200.000 [ns/GB] * VOL[GB] )