Investigate performance of proving for padded height $2^{22}$ and 2^{23}$

[Sword-Smith]

Running both with and without TVM_LDE_TRACE="no_cache", I've seen some quite troubling performance numbers for proving when the padded height is $2^{23}$. We should get performance numbers and RAM consumption for these three padded heights and investigate: $2^{21}$ (for reference), $2^{22}$, and $2^{23}$.

Specifically, a user with 2TB RAM and 256 cores reports that proving for a padded height of $2^{23}$ takes two hours where it, by my calculations, should take less than 600 seconds. And I ran out of RAM when attempting to create these proofs, even with TVM_LDE_TRACE="no_cache" and having 768GB RAM, which should be plenty for this configuration.

[jan-ferdinand]

Do you have insight into the various tables' heights, the program being run, etc.?

[Sword-Smith]

The behavior was observed when running a SingleProof program with many inputs, which translates to the verification of many correct executions of RemovalRecordIntegrity.

This piece of code exhibits the problem, for a padded height of $2^{23}$:
Neptune-Crypto/neptune-core@ec9e693#diff-b03414229c3f4a14c7601dfee113a82c91419c0d1f5fe4181835d6609650f2edR1587-R1600

Edit: The above-marked function call in the test crashes on our hardware, though: Even with 768GB RAM and TVM_LDE_TRACE="no_cache". A way forward would be to run it with live time reporting activated to see where the problems occur.

[jan-ferdinand]

Can you extract the VM's initial state or the (program, input, non-determinism)-triple from this function? That would allow analysis in Triton CLI.

[marco-storswift]

[prove]padded_height took=8388608
LDE 67108864 took=6.98µs/123.88s/9.00s/18.56s
lde master took=152.57s

prove padded_height took=8388608
LDE 67108864 took=22.76µs/10878.94s/8.91s/18.93s
lde master took=10908.07s
The same machine, the same software, but different proofs have very different time consumptions. I calculated the time consumption and it seems to be the NTT part. I hope this problem can be found.

[jan-ferdinand]

Is there any difference between the programs you were proving the correct execution of? If so, would you mind sharing what they are?

[marco-storswift]

Is there any difference between the programs you were proving the correct execution of? If so, would you mind sharing what they are?您证明正确执行的程序之间有什么区别吗？如果是这样，您介意分享它们是什么吗？

I just use neptune-cli to perform the send transfer operation. I estimate that the number of inputs is about 10.

[jan-ferdinand]

I'm not sure what that means in terms of Triton VM program or Triton VM input. Could you run neptune-core with the environment variable TASMLIB_TRITON_TUI set?¹ Once you encounter the stalling program, could you either send the vm_state.json that is now written to disk my way, or alternatively, run additional analysis using the Triton CLI? I'd be particularly interested in triton-cli --profile prove --initial-state vm_state.json and also in triton-cli --profile run --initial-state vm_state.json.

Footnotes

1. On linux, run TASMLIB_TRITON_TUI=1 neptune-core --your-usual-params. On windows, first run Set-Variable TASMLIB_TRITON_TUI 1, then run your usual neptune-core command. ↩

[marco-storswift]

let start3 = Instant::now();
profiler!(start "evaluation");
Zip::from(extended_columns.axis_iter_mut(Axis(1)))
.and(interpolation_polynomials.axis_iter(Axis(0)))
.par_for_each(|lde_column, interpolant| {
let lde_codeword = evaluation_domain.evaluate(&interpolant[()]);
Array1::from(lde_codeword).move_into(lde_column);
});
let start4 = Instant::now();
let _ = writeln!(stderr(), "LDE {} took={:.2?}/{:.2?}/{:.2?}/{:.2?} ", num_rows,
Instant::now() - start4,
start4 - start3,
start3 - start2,
start2 - start1);
//error
prove padded_height took=8388608
LDE 67108864 took=22.07µs/7604.13s/16.30s/23.78s
lde master took=7645.37s
LDE 67108864 took=23.36µs/66.76s/11.42s/17.24s
lde aux took=96.29s
//nomoral
prove padded_height took=8388608
LDE 67108864 took=5.89µs/99.48s/16.32s/22.64s
lde master took=139.56s
LDE 67108864 took=5.38µs/65.17s/11.36s/16.30s
lde aux took=93.56s

[jan-ferdinand]

I understand that you are having trouble. I cannot reproduce the issue. The code dump does not give me any further insight. Could you please provide me with the information I ask for in this comment?

Alternatively, how did you get the results from the code dump? Can you point me to some git repository that I can use to reproduce the issue?

How often do you observe the issue? Is your system doing anything else when you observe the issue?

[marco-storswift]

I understand that you are having trouble. I cannot reproduce the issue. The code dump does not give me any further insight. Could you please provide me with the information I ask for in this comment?

Alternatively, how did you get the results from the code dump? Can you point me to some git repository that I can use to reproduce the issue?

How often do you observe the issue? Is your system doing anything else when you observe the issue?

please check the email. i had sent vm_state.json by email

[jan-ferdinand]

I have generated 10 proofs for the execution of the initial VM state you have provided me with. The time it took to generate these proofs was not jittery at all. To back this statement up, here are some statistics regarding the proving times:

statistic	time [s]
Mean	200.943
Median	200.750
Standard Deviation	0.506	(!)
Minimum	200.240
Maximum	201.880

The padded height of the algebraic execution trace for the above proofs was $2^{22}$. To be more precise, here are the table heights:

Table	Height
Program	119730
Processor	2281756
OpStack	1944462
Ram	3214368
JumpStack	2281756
Hash	1112088
Cascade	65536
Lookup	256
U32	468980

I have also generated 17 proofs for the execution of the below program with input 256 000, which results in a padded height of $2^{23}$.

sponge_init read_io 1 call spin halt

// BEFORE: _ n
// AFTER:  _ 0
spin:
  sponge_squeeze               // _ n [_; 10]
  write_mem 5 write_mem 4      // _ n [_; 1]
  split pop 2                  // _ n
  dup 0 push 0 eq skiz return
  addi -1 recurse

To be more precise, it results in the following table heights:

Table	Height
Program	30
Processor	2816014
OpStack	6656027
Ram	2304009
JumpStack	2816014
Hash	1536025
Cascade	65536
Lookup	256
U32	8361966

For this padded height also, I could not observe any significant jitter. Also here, some statistics:

statistic	time [s]
Mean	420.558
Mode	421.930
Median	420.470
Standard Deviation	1.140	(!)
Minimum	418.990
Maximum	422.500

In addition to all that, I have investigated the scaling of the individual sub-functions of the prover as a function of the padded height. You can click on the picture to enlarge it.

While there are some unexpected jumps (in particular, step “out-of-domain rows” from padded height $2^{20}$ to $2^{21}$), I cannot observe any dramatic performance drop-off.

All in all, I am still unable to reproduce any scaling issue with Triton VM.