distributed - 提高 bigint 写入磁盘性能

Question

我正在处理非常大的bigint数字，我需要将它们写入磁盘并稍后再读取它们，因为它们一次无法全部放入内存中。

当前的 Chapel 实现首先将 a 转换bigint为 a string，然后将其写入string磁盘 [1]。对于大整数来说，这需要很长时间。

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

有没有办法使用 GMP 的mpz_out_raw()/ mpz_inp_raw()[2] 或mpz_export()/ mpz_import()[3] 或其他类似的方式将bigint' 的字节直接转储到磁盘而不事先转换为字符串，然后将字节读回bigint对象？

这也适用于bigint数组吗？

如果在当前状态下不可能，如何将这样的功能添加到 Chapel 的标准库中？

[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

score 3 · Accepted Answer

您提到的功能在任何 Chapel 模块中都不能直接使用，但您可以编写过程extern和extern类型来直接访问这些GMP功能。

首先，我们需要能够使用 C 文件，因此为它们声明一些过程和类型：

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

然后我们可以声明我们需要的GMP函数：

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;

现在我们可以使用它们来写一个bigint值：

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);

并从文件中读回：

var readIt: bigint;

f = fopen("gmp_outfile", "r");
mpz_inp_raw(readIt.mpz, f);
fclose(f);

writeln("Read the number:", readIt);

对于bigint值数组，只需循环它们以写入或读取它们：

// 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);

score -5 · Accepted Answer

序言：
数据size是静态属性，但流量永远是我们最大的敌人。

“这样的功能可以添加到 Chapel 的标准库中吗？ ”

以当前价格增加几个单位，数十甚至数百[TB]-s 的 RAM 容量，恕我直言，问题永远无法通过上述方向的任何语言扩展来解决。

为什么从来没有？由于爆炸性的成本：

如果一个人只花几分钟时间了解事实，下面的延迟图就会出现在一张白纸上。虽然各自的数字可能会有所不同，但信息在数量级和思维过程的依赖链中：

            ________________________________________________________________________________________
           /                                                                                       /
          /                   ________________________________________________________            / 
         /                   /                                                       /           /  
        /                   /          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]

最后但同样重要的是，只需计算此类步骤对<< 1.0加速的影响

给定原始处理 take XYZ [ns]，
“修改”处理将采取：

                          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]

因此，这种受到不利影响的性能将受到损害（如阿姆达尔定律所示）：

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

distributed - 提高 bigint 写入磁盘性能

2 回答 2

Related

Reference