Some questions about Dory setup

[Lengxiaoyi]

Background and Motivation

Hi, when I run the example example using only the CPU, I find that when I set const DORY_SETUP_MAX_NU: usize = 13, the time will only consume roughly 10s, and when I set it to 15, the time consumes 49s, and the performance of the CPU I'm using is pretty much the same as described in the code, but when I use the blitzar feature I find that the time transformations can increase by 2 squares with the DORY_SETUP_MAX_NU number setting, which is not GPU enabled in the dory setting. The time transform can increase by 2 squares with the number setting of DORY_SETUP_MAX_NU, the GPU was not enabled at the time of the dory setting I can't pinpoint the cause of the problem need your help, good luck!

Changes Required

Please help me understand this.

[JayWhite2357]

Hey @Lengxiaoyi,
The reason that the setup takes much longer when the GPU is enabled is that blitzar does a one-time precomputation in order for the GPU to be more efficient. This precomputation is very large, but can be saved and later loaded from a file. The reason that the CPU is so much faster is that it doesn't do this precomputation because it has blitzar disabled.

We have published a few of these parameters here: https://github.com/spaceandtimelabs/sxt-proof-of-sql/releases/tag/dory-prover-params-nu-16 (or https://github.com/spaceandtimelabs/sxt-proof-of-sql/releases/tag/max-nu-14). But, you can do it youself.

Take a look at this: https://github.com/spaceandtimelabs/sxt-proof-of-sql/tree/main/crates/proof-of-sql/utils/generate-parameters.

[Lengxiaoyi]

Thank you very much for your reply, I didn't notice that part and now I can understand it.XD～

[babu88-az]

Hi there,

It seems you're encountering a performance scaling issue related to the DORY_SETUP_MAX_NU parameter and the use of the Blitzar feature. Let me address your observations and provide guidance:

---

Understanding the Problem

1. Nonlinear Scaling with DORY_SETUP_MAX_NU:

   • The significant increase in time (e.g., 10 seconds to 49 seconds when increasing DORY_SETUP_MAX_NU from 13 to 15) suggests that the computation complexity grows non-linearly, likely quadratic or worse.
   • This could be due to algorithmic inefficiencies or increased memory and computational overhead as the problem size grows.

2. Blitzar Feature Impact:

   • You observed that the Blitzar feature causes transformations to scale even more dramatically with DORY_SETUP_MAX_NU. Since Blitzar does not enable the GPU in this configuration, it likely introduces additional steps or complexity that exacerbate scaling issues.

3. Hardware Performance:

   • Given that your CPU performance aligns with the expected baseline, this seems to be a software-level issue (e.g., in the implementation or configuration of Blitzar and DORY_SETUP_MAX_NU handling).

---

Potential Causes

1. Algorithmic Complexity:

   • The Blitzar feature might introduce steps with higher computational complexity, such as matrix operations or iterative transformations that scale poorly with DORY_SETUP_MAX_NU.

2. Memory Bottlenecks:

   • Larger values of DORY_SETUP_MAX_NU could result in higher memory usage, causing cache misses or increased swapping, which significantly slows down processing.

3. Threading or Parallelism Issues:

   • If the implementation uses multithreading or parallelism, scaling issues might arise from thread contention, inefficient load balancing, or synchronization overhead.

4. I/O or Intermediate Processing:

   • Blitzar might involve intermediate processing steps or I/O operations that scale poorly with DORY_SETUP_MAX_NU.

---

Suggested Steps to Diagnose and Resolve

1. Profile the Code:

   • Use a CPU profiler (e.g., perf, gprof, or Visual Studio Profiler) to identify bottlenecks. Look for hotspots in the Blitzar feature or functions handling DORY_SETUP_MAX_NU.

2. Analyze Algorithmic Complexity:

   • Review the code to ensure the steps scale appropriately with DORY_SETUP_MAX_NU.
   • Consider simplifying or optimizing expensive operations.

3. Check Memory Usage:

   • Monitor memory consumption to identify potential issues with allocation, caching, or paging.

4. Experiment with Smaller Steps:

   • Increment DORY_SETUP_MAX_NU in smaller steps to observe when the scaling behavior starts to deviate significantly. This might help isolate specific thresholds where inefficiencies arise.

5. Verify Multithreading Behavior:

   • If the implementation uses threading, check for contention or imbalance. Tools like htop or thread analysis tools can help.

6. Engage with the Community:

   • If the problem persists, consider sharing your profiling results or findings with the maintainers or community of the project. They might provide insights or confirm known issues.

---

Changes Required

If the issue lies in scaling, you might need to:

• Optimize the algorithm: Replace inefficient operations with more scalable alternatives.
• Limit DORY_SETUP_MAX_NU: Enforce a practical upper limit to prevent unmanageable scaling.
• Improve Blitzar integration: Ensure the feature operates efficiently without unintended overhead.

---

Good luck! Let me know if you'd like help profiling or analyzing specific parts of the code.