Hi Itaru,
The problem we had with std::vector was how it allocates memory. When the memory allocated for a vector is full, its capacity is increased by allocating a bigger chunk of memory (commonly with double the capacity of the original vector), and all elements are moved to the new allocation.
We observed that when connections are all put in one big vector, and the number of connections in the vector becomes large, memory consumption from vector growth becomes problematic. We therefore created a new container, BlockVector, to keep memory consumption under control and avoid moving the elements when increasing the capacity. The BlockVector achieves this by allocating an entire block of a fixed size every time the capacity has to be increased. The BlockVector therefore becomes a vector of vectors, where the entire size of each new block, which is a new vector in the vector of vectors, is allocated only once when the block is created.
Some benchmarks were done during the review of the PR,
https://github.com/nest/nest-simulator/pull/1047
You can find the benchmarks here:
https://github.com/nest/nest-simulator/files/2505835/Bench_214_sq_db70dcc1ed...
Note that BlockVector was called "Seque" at the time.
Best, Håkon ________________________________ From: Itaru Kitayama itaru.kitayama@gmail.com Sent: 10 August 2021 05:51 To: NEST User Mailing List users@nest-simulator.org Subject: [NEST Users] libnestutil BlockVector Implementation
Hello Håkon,
As you implemented, an instance of BlockVector is a vector of vectors but allows users to specify with one index. As I am having a few problems with mapping BlockVetors to the device memory, I am simply wondering as to why we can't just use std::vector< value_type >? If you guys observed significant performance improvements with BlockVectors in the past, would you mind pointing me to the papers or notes?
Thanks, Itaru. _______________________________________________ NEST Users mailing list -- users@nest-simulator.org To unsubscribe send an email to users-leave@nest-simulator.org
Håkon, Are you sure there’s stil no equivalent implementations in std::? If that’s the case we don’t need to carry/maintain our code, but the GCC folk do.
Thanks for the pointers!
Itaru.
On Tue, Aug 10, 2021 at 20:35 Håkon Mørk hakon.mork@nmbu.no wrote:
Hi Itaru,
The problem we had with std::vector was how it allocates memory. When the memory allocated for a vector is full, its capacity is increased by allocating a bigger chunk of memory (commonly with double the capacity of the original vector), and all elements are moved to the new allocation.
We observed that when connections are all put in one big vector, and the number of connections in the vector becomes large, memory consumption from vector growth becomes problematic. We therefore created a new container, BlockVector, to keep memory consumption under control and avoid moving the elements when increasing the capacity. The BlockVector achieves this by allocating an entire block of a fixed size every time the capacity has to be increased. The BlockVector therefore becomes a vector of vectors, where the entire size of each new block, which is a new vector in the vector of vectors, is allocated only once when the block is created.
Some benchmarks were done during the review of the PR,
https://github.com/nest/nest-simulator/pull/1047
You can find the benchmarks here:
https://github.com/nest/nest-simulator/files/2505835/Bench_214_sq_db70dcc1ed...
Note that BlockVector was called "Seque" at the time.
Best, Håkon
*From:* Itaru Kitayama itaru.kitayama@gmail.com *Sent:* 10 August 2021 05:51 *To:* NEST User Mailing List users@nest-simulator.org *Subject:* [NEST Users] libnestutil BlockVector Implementation
Hello Håkon,
As you implemented, an instance of BlockVector is a vector of vectors but allows users to specify with one index. As I am having a few problems with mapping BlockVetors to the device memory, I am simply wondering as to why we can't just use std::vector< value_type >? If you guys observed significant performance improvements with BlockVectors in the past, would you mind pointing me to the papers or notes?
Thanks, Itaru. _______________________________________________ NEST Users mailing list -- users@nest-simulator.org To unsubscribe send an email to users-leave@nest-simulator.org _______________________________________________ NEST Users mailing list -- users@nest-simulator.org To unsubscribe send an email to users-leave@nest-simulator.org
Hi Itaru,
The closest standard library implementation is std::deque. However, random access with std::deque is inefficient, which caused it to slow down simulations. We also experimented with different growth factors for std::vector, but that didn't completely solve the problem. That is why we landed on implementing BlockVector.
Best, Håkon ________________________________ From: Itaru Kitayama itaru.kitayama@gmail.com Sent: 10 August 2021 13:59 To: NEST User Mailing List users@nest-simulator.org Subject: [NEST Users] Re: libnestutil BlockVector Implementation
Håkon, Are you sure there’s stil no equivalent implementations in std::? If that’s the case we don’t need to carry/maintain our code, but the GCC folk do.
Thanks for the pointers!
Itaru.
On Tue, Aug 10, 2021 at 20:35 Håkon Mørk <hakon.mork@nmbu.nomailto:hakon.mork@nmbu.no> wrote: Hi Itaru,
The problem we had with std::vector was how it allocates memory. When the memory allocated for a vector is full, its capacity is increased by allocating a bigger chunk of memory (commonly with double the capacity of the original vector), and all elements are moved to the new allocation.
We observed that when connections are all put in one big vector, and the number of connections in the vector becomes large, memory consumption from vector growth becomes problematic. We therefore created a new container, BlockVector, to keep memory consumption under control and avoid moving the elements when increasing the capacity. The BlockVector achieves this by allocating an entire block of a fixed size every time the capacity has to be increased. The BlockVector therefore becomes a vector of vectors, where the entire size of each new block, which is a new vector in the vector of vectors, is allocated only once when the block is created.
Some benchmarks were done during the review of the PR,
https://github.com/nest/nest-simulator/pull/1047
You can find the benchmarks here:
https://github.com/nest/nest-simulator/files/2505835/Bench_214_sq_db70dcc1ed...
Note that BlockVector was called "Seque" at the time.
Best, Håkon ________________________________ From: Itaru Kitayama <itaru.kitayama@gmail.commailto:itaru.kitayama@gmail.com> Sent: 10 August 2021 05:51 To: NEST User Mailing List <users@nest-simulator.orgmailto:users@nest-simulator.org> Subject: [NEST Users] libnestutil BlockVector Implementation
Hello Håkon,
As you implemented, an instance of BlockVector is a vector of vectors but allows users to specify with one index. As I am having a few problems with mapping BlockVetors to the device memory, I am simply wondering as to why we can't just use std::vector< value_type >? If you guys observed significant performance improvements with BlockVectors in the past, would you mind pointing me to the papers or notes?
Thanks, Itaru. _______________________________________________ NEST Users mailing list -- users@nest-simulator.orgmailto:users@nest-simulator.org To unsubscribe send an email to users-leave@nest-simulator.orgmailto:users-leave@nest-simulator.org _______________________________________________ NEST Users mailing list -- users@nest-simulator.orgmailto:users@nest-simulator.org To unsubscribe send an email to users-leave@nest-simulator.orgmailto:users-leave@nest-simulator.org
-
Håkon Mørk -
Itaru Kitayama