m4ri becomes very slow when a lot of matrices are created

[smunaut]

I was dealing with a precomputation for a crypto attack that creates around 2^17 matrices and keeps them in memory ...

I noticed a 10x slow down of the alogithm when all those matrices are created ... I'm not sure exactly what operations are slowed down, but clearly something is.

My current work around was to create one single HUGE matrix instead of 2^17 "small" ones and that worked out fine. At least documenting that behavior could be useful (is it documented and did I miss it ?)

[Martin Albrecht]

Can you give some code which allows to reproduce the problem? Right now, I cannot tell which algorithm you are talking about etc.

[smunaut]

I was talking about my algorigthm :)

I think it's the mzd_init and mzd_free that are slowed down a lot.

Example software attached. It does a simple alloc/dealloc test and times it. It does it once. Then allocate 64k dummy matrices and does it again, then frees the dummy matrices and does it a third time, and you can see a large slow down when there are 64k unused matrices allocated.

5 ms 521 ms 7 ms

[Martin Albrecht]

Right, so it seems its our caching stuff. We allocate mzd_t's in blocks of 64 to save some time creating small matrices. We keep those in a cache object which is in a list of cache objects. We have no limit on how many of these we are creating, but we probably should (cf. mzd_t_malloc/mzd_t_free).

I'll try to take a closer look tomorrow.

[smunaut]

Great !

BTW, thanks a lot for this library, it's pretty awesome ! :)

[Martin Albrecht]

limit size of mzd_t cache to 16*64 (fixes #40)

→ Wiki macro error: Changeset 194e2b2e55a6 not found.