Skip to content
Snippets Groups Projects

Mitigate memory allocations in Calo Graph Clustering

Merged Andre Gunther requested to merge gunther_fixMallocGraph into master
@@ -17,6 +17,9 @@
#include "Gaudi/Algorithm.h"
#include "Kernel/CaloCellID.h"
#include "LHCbAlgs/Transformer.h"
#include "LHCbMath/SIMDWrapper.h"
#include "boost/container/flat_map.hpp"
#include "boost/container/small_vector.hpp"
#include "boost/dynamic_bitset.hpp"
#include <map>
#include <vector>
@@ -30,44 +33,55 @@
namespace LHCb::Calo {
namespace {
typedef std::map<int, float> WeightedEdge;
using WeightedEdge = boost::container::flat_map<int, float>;
using boost::container::small_vector;
using simd = SIMDWrapper::best::types;
template <typename Container>
auto simd_find( const Container& vec, simd::int_v value ) {
for ( size_t i{0}; i < vec.size(); i += simd::size ) {
if ( const auto mask = ( simd::int_v{vec.data() + i} == value ); any( mask ) )
return any( mask && simd::loop_mask( i, vec.size() ) );
}
return false;
}
/**
* @brief Graph representing ECAL cells
* @details The constant graph size of 6016 is given by the total number of readout cells from the ECAL.
*/
class Graph {
std::vector<std::vector<int>> m_adj_u; // Pointer to an array containing adjacency vectors
std::vector<WeightedEdge> m_adj_weighted;
std::vector<WeightedEdge> m_adj_weighted_pred;
static constexpr size_t m_size{6016};
std::vector<small_vector<int, 8>> m_adj_u; // Pointer to an array containing adjacency vectors
std::vector<WeightedEdge> m_adj_weighted;
std::vector<WeightedEdge> m_adj_weighted_pred;
void DFSUtil( int v, boost::dynamic_bitset<>& visited, LHCb::span<std::vector<int>> conComp,
int index ) const; // A function used by DFS
public:
explicit Graph( size_t V );
void addEdge( int v, int w, float weight );
std::vector<std::vector<int>> connectedComponents() const;
std::vector<int> outEdgesMap( int node );
explicit Graph() : m_adj_u( m_size ), m_adj_weighted( m_size ), m_adj_weighted_pred( m_size ) {}
void addEdge( int v, int w, float weight );
auto connectedComponents() const;
void calculateWeights( LHCb::span<const int> nodes, const LHCb::Event::Calo::Digits& digits );
int outEdgesSize( int node ) { return m_adj_weighted[node].size(); }
int inEdgesSize( int node ) { return m_adj_weighted_pred[node].size(); }
size_t size() const { return m_adj_u.size(); }
int outEdgesSize( int node ) const { return m_adj_weighted[node].size(); }
int inEdgesSize( int node ) const { return m_adj_weighted_pred[node].size(); }
size_t size() const { return m_size; }
WeightedEdge const& adjWeightedPred( int index ) const { return m_adj_weighted_pred[index]; }
WeightedEdge const& adjWeighted( int index ) const { return m_adj_weighted[index]; }
};
Graph::Graph( size_t V ) : m_adj_u{V}, m_adj_weighted{V}, m_adj_weighted_pred{V} {}
void Graph::addEdge( int v, int w, float weight ) {
m_adj_u[v].emplace_back( w );
m_adj_u[w].emplace_back( v );
m_adj_u[v].push_back( w );
m_adj_u[w].push_back( v );
m_adj_weighted[v][w] = weight;
m_adj_weighted_pred[w][v] = weight;
}
// Method to get connected components in an undirected graph
std::vector<std::vector<int>> Graph::connectedComponents() const {
std::vector<std::vector<int>> conComp{size()};
auto V = size();
boost::dynamic_bitset<> visited{V}; // Mark all the vertices as not visited
for ( size_t v = 0; v < V; v++ ) {
auto Graph::connectedComponents() const {
std::vector<std::vector<int>> conComp( m_size );
boost::dynamic_bitset<> visited( m_size ); // Mark all the vertices as not visited
for ( size_t v = 0; v < m_size; v++ ) {
if ( !visited[v] && !m_adj_u[v].empty() ) {
DFSUtil( v, visited, conComp, v ); // Look all reachable vertices from v
}
@@ -85,35 +99,32 @@ namespace LHCb::Calo {
}
}
std::vector<int> Graph::outEdgesMap( int node ) {
std::vector<int> nodes;
nodes.reserve( m_adj_weighted[node].size() );
for ( auto const& n : m_adj_weighted[node] ) { nodes.emplace_back( n.first ); }
return nodes;
}
void Graph::calculateWeights( LHCb::span<const int> nodes, const LHCb::Event::Calo::Digits& digits ) {
std::map<int, float> seedToClEnergy;
for ( auto n : nodes ) {
auto edges = outEdgesMap( n );
const auto& edges = m_adj_weighted[n];
if ( edges.size() < 2 ) continue;
for ( auto e : edges ) {
if ( seedToClEnergy.find( e ) != seedToClEnergy.end() ) continue;
auto cell = digits.find( DenseIndex::details::toCellID( e ) );
const auto& cells = m_adj_weighted_pred[e];
float energy = std::accumulate( cells.begin(), cells.end(), cell ? cell->energy() : 0.f,
auto totalEnergy{0.f};
for ( auto ed : edges ) {
const auto e = ed.first;
if ( const auto energy_e = seedToClEnergy.find( e ); energy_e != seedToClEnergy.end() ) {
totalEnergy += energy_e->second;
continue;
}
auto cell = digits.find( DenseIndex::details::toCellID( e ) );
const auto& cells = m_adj_weighted_pred[e];
float energy = std::accumulate( cells.begin(), cells.end(), cell ? cell->energy() : 0.f,
[&]( float energy, const auto& te ) {
auto cell = digits.find( DenseIndex::details::toCellID( te.first ) );
return cell ? energy + cell->energy() : energy;
} );
[[maybe_unused]] auto r = seedToClEnergy.emplace( e, energy );
totalEnergy += energy;
[[maybe_unused]] auto r = seedToClEnergy.emplace( e, energy );
assert( r.second );
}
float totalEnergy = std::accumulate( edges.begin(), edges.end(), 0.f, [&]( float e, const auto& edge ) {
return e + seedToClEnergy.at( edge );
} );
for ( auto e : edges ) {
auto weight = seedToClEnergy.at( e ) / totalEnergy;
for ( auto ed : edges ) {
const auto e = ed.first;
auto weight = seedToClEnergy.at( e ) / totalEnergy;
m_adj_weighted[n][e] = weight;
m_adj_weighted_pred[e][n] = weight;
}
@@ -182,6 +193,7 @@ namespace LHCb::Calo {
std::vector<std::pair<float, LHCb::Calo::CellID>> sortedDigits;
sortedDigits.reserve( digits.size() );
std::vector<int> mergedPi0;
mergedPi0.reserve( 1024 );
/// Sort the digits by energy
for ( auto digit : digits ) {
@@ -190,25 +202,25 @@ namespace LHCb::Calo {
std::sort( sortedDigits.begin(), sortedDigits.end(), std::greater<>{} );
/// Graph declaration and sorted digit insertion under rules
Graph G{6016};
Graph G{};
for ( auto [energy, id] : sortedDigits ) {
if ( G.outEdgesSize( denseIndex( id ) ) == 0 ) {
if ( const auto dense_id = denseIndex( id ); G.outEdgesSize( dense_id ) == 0 ) {
for ( auto n : detector.neighborCells( id ) ) {
auto cell = digits.find( n );
if ( cell && energy > cell->energy() ) {
G.addEdge( denseIndex( n ), denseIndex( id ), 1. );
G.addEdge( denseIndex( n ), dense_id, 1.f );
if ( energy > m_pi0_min_seed_e.value() && ( cell->energy() * 100 / energy ) > m_pi0_min_f1.value() ) {
mergedPi0.emplace_back( denseIndex( id ) );
mergedPi0.emplace_back( dense_id );
mergedPi0.emplace_back( denseIndex( n ) );
}
}
}
} else if ( std::find( mergedPi0.begin(), mergedPi0.end(), denseIndex( id ) ) != mergedPi0.end() ) {
auto seed = G.outEdgesMap( denseIndex( id ) )[0];
} else if ( simd_find( mergedPi0, simd::int_v{dense_id} ) ) {
const auto seed = G.adjWeighted( dense_id ).begin()->first;
for ( auto n : detector.neighborCells( id ) ) {
auto cell = digits.find( n );
if ( cell && energy > cell->energy() && G.outEdgesSize( denseIndex( cell->cellID() ) ) == 0 ) {
G.addEdge( denseIndex( n ), seed, 1. );
G.addEdge( denseIndex( n ), seed, 1.f );
}
}
}
Loading