search

encryptogroup / SEEC

SEEC: Memory-Safety Meets Efficiency in Secure Two-Party Computation
MIT License
6 stars 0 forks source link

Sub-Linear memory for BaseLayerIterator #16

Open robinhundt opened 7 months ago

robinhundt commented 7 months ago

In https://github.com/encryptogroup/SEEC/commit/1ba607ed27b6fdb449b1fefa5fca0d909d324068 we already improved the BaseLayerIter. However, there is an easy improvement we could do to the iteration code to reduce the memory from O(|base_circuit|) to something less than that. Currently, this linear memory cost is due to storing the inputs needed for each gate in a flat vec and calculating this for each gate in constructor. A, hopefully, better way would be to store a mapping of HashMap<GateId, u32> where we only store the inputs needed for gates of which at least one predecessor has already been processed and remove them when they are zero. The intuition is that a gate for which no predecessor has been processed can't be yielded and once we yield a gate we can not yield it again, thus we don't need to store how many inputs are needed for these gates. Albeit a little more computationally costly, this should significantly reduce the memory cost of iteration objects for large base circuits.

robinhundt commented 6 months ago

Hi, sorry for the late reply. Yes, you can definitely give it a try. If you have questions, don't hesitate yo ask. The last weeks were stressful, but I have more time now :)