Memory allocation error using co/stl containers (co::vector, co::hash_map) #349

piperoc · 2023-11-14T00:22:40Z

I wrote a simple graph class using the co::vector and the co::hash_map to use a common adjacency list technique.

I then created a unit test like the the other files in your unitest source folder.

All tests pass but at the very end I get what looks like a memory allocation error (it's probably my mistake in using those structures).
I tried to profile it but cannot figure it out.

Here's my class:

file: graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include "cout.h"
#include "stl.h"
#include "log.h"


template <typename VertexType, typename IDType>
class Graph {

public:
    /// @brief default constructor
    Graph() = default;


    /// @brief add a vertex to the graph
    /// @param IdType the vertex id to be added
    /// @param VertexType the vertex to be added
    void addVertex(const IDType& id, const VertexType& vertex) {
        if (vertexMap.find(id) != vertexMap.end()) {
            ELOG << "vertex " << id << " already exists";
            return;
        }
        vertices.push_back(vertex);
        vertexMap[id] = vertices.size() - 1;
        adjacencyLists.push_back(co::vector<IDType>());
    }


    /// @brief add an edge to the graph
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    void addEdge(const IDType& source, const IDType& target) {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return;
        }
        adjacencyLists[vertexMap[source]].push_back(target);
    }

    /// @brief get a node by id
    /// @param IDType the vertex id
    /// @return VertexType the vertex
    VertexType findNode(const IDType& id) const {
        if (vertexMap.find(id) == vertexMap.end()) {
            ELOG << "vertex " << id << " does not exist";
            return VertexType();
        }
        return vertices[vertexMap.at(id)];
    }

    /// @brief remove a node by id
    /// @param IDType the vertex id
    void removeNode(const IDType& id) {
        if (vertexMap.find(id) == vertexMap.end()) {
            ELOG << "vertex " << id << " does not exist";
            return;
        }
        size_t index = vertexMap.at(id);
        vertices.erase(vertices.begin() + index);
        vertexMap.erase(id);
        adjacencyLists.erase(adjacencyLists.begin() + index);
        for (auto& list : adjacencyLists) {
            for (auto& node : list) {
                if (node == id) {
                    node = adjacencyLists.size();
                }
                if (node > index) {
                    node--;
                }
            }
        }
    }

    /// @brief remove an edge by id
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    void removeEdge(const IDType& source, const IDType& target) {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return;
        }
        size_t sourceIndex = vertexMap.at(source);
        size_t targetIndex = vertexMap.at(target);
        for (auto& node : adjacencyLists[sourceIndex]) {
            if (node == target) {
                node = adjacencyLists.size();
            }
            if (node > targetIndex) {
                node--;
            }
        }
    }


    /// @brief VertexMap getter
    /// @return co::map<IDType, size_t> the vertex map
    co::hash_map<IDType, size_t> VertexMap() const {
        return vertexMap;
    }

    /// @brief Vertices getter
    /// @return co::vector<VertexType> the vertices
    co::vector<VertexType> Vertices() const {
        return vertices;
    }

    /// @brief Edges getter
    /// @return co::vector<co::vector<IDType>> the adjacency lists
    co::vector<co::vector<IDType>> Edges() const {
        return adjacencyLists;
    }

    /// @brief function to check if an edge exists between two vertices
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    /// @return bool true if the edge exists, false otherwise
    bool hasEdge(const IDType& source, const IDType& target) const {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return false;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return false;
        }
        size_t sourceIndex = vertexMap.at(source);
        for (auto& node : adjacencyLists[sourceIndex]) {
            if (node == target) {
                return true;
            }
        }
        return false;
    }


private:
    /// @brief vertex list
    co::vector<VertexType> vertices;

    /// @brief vertex map
    co::hash_map<IDType, size_t> vertexMap;

    /// @brief adjacency lists representing the graph
    co::vector<co::vector<IDType>> adjacencyLists;
};


#endif // GRAPH_H

and here's the file implementing the tests:

file: graph.h

#include "co/flag.h"
#include "co/cout.h"
#include "co/log.h"
#include "co/unitest.h"
#include "co/fastring.h"
#include "co/mem.h"
#include "co/graph.h"
#include <chrono>


namespace test {

DEF_test(graph) {

	Graph<std::string, uint32_t> myGraph = Graph<std::string, uint32_t>();

        myGraph.addVertex(1, "a");
        myGraph.addVertex(2, "b");
        myGraph.addVertex(3, "c");
        myGraph.addVertex(4, "d");

        myGraph.addEdge(1, 2);
        myGraph.addEdge(2, 3);
        myGraph.addEdge(3, 4);
        myGraph.addEdge(4, 1);
        myGraph.addEdge(2, 4);
        myGraph.addEdge(4, 2);

    DEF_case(check_vertices) {
		
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]],"a");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]],"b");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]],"c");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]],"d");

    }

	DEF_case(find_node) {

		auto result = myGraph.findNode(3);
		EXPECT_EQ(result , "c");
	}

	DEF_case(find_node_not_found) {

		auto result = myGraph.findNode(5);
		EXPECT_EQ(result, "");
	}

	
	DEF_case(huge_graph) {
		
		const int NUMBER_OF_VERTICES = 2000;

		Graph<std::string, uint32_t> bigGraph;

		auto start = std::chrono::high_resolution_clock::now();

		for (int i = 0; i < NUMBER_OF_VERTICES; i++) {
			bigGraph.addVertex(i, "Vertex_" + std::to_string(i));
		}

		for (int sourceID = 1; sourceID <= NUMBER_OF_VERTICES; ++sourceID) {
			for (int targetID = 1; targetID <= NUMBER_OF_VERTICES; ++targetID) {
				// add 4 edges per vertex
                if (targetID  == (sourceID -1) || targetID == (sourceID +1) || targetID == (sourceID -2) || targetID == (sourceID +2)) 
						bigGraph.addEdge(sourceID, targetID);
			}
		}

		auto end = std::chrono::high_resolution_clock::now();
		auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

		cout << "Time taken to create the big graph: " << duration.count() << " microseconds" << std::endl;

		std::string halfwayVertex = "Vertex_" + std::to_string(NUMBER_OF_VERTICES/2);
		start = std::chrono::high_resolution_clock::now();
		auto result = bigGraph.findNode(NUMBER_OF_VERTICES/2);
		end = std::chrono::high_resolution_clock::now();
		duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
		cout << "Time taken to find node: " << duration.count() << " microseconds" << std::endl;
		EXPECT_EQ(result, halfwayVertex);

	}
    
}


} // namespace test

When I run the unit tests I get the following

> begin test: graph
 case check_vertices:
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]], "a") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]], "b") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]], "c") passed
  EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]], "d") passed
 case find_node:
  EXPECT_EQ(result, "c") passed
 case find_node_not_found:
  EXPECT_EQ(result, "") passed
 case huge_graph:
Time taken to create the big graph: 7080 microseconds
Time taken to find node: 1 microseconds
  EXPECT_EQ(result, halfwayVertex) passed
free(): invalid size
F1113 18:59:22.230] SIGABRT: aborted
Aborted

if I debug it aborts when calling void _destruct_range from the co::vector class (file include/co/vector.h line 322) as the for loop range that I'm indirectly passing (with the destructor) is probably wrong.

call stack

[...]
libc.so.6!__GI_raise(int sig) (\build\glibc-CVJwZb\glibc-2.27\sysdeps\unix\sysv\linux\raise.c:51)
libc.so.6!__GI_abort() (\build\glibc-CVJwZb\glibc-2.27\stdlib\abort.c:79)
libc.so.6!__libc_message(enum __libc_message_action action, const char * fmt) (\build\glibc-CVJwZb\glibc-2.27\sysdeps\posix\libc_fatal.c:181)
libc.so.6!malloc_printerr(const char * str) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:5342)
libc.so.6!_int_free(int have_lock, mchunkptr p, mstate av) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:4171)
libc.so.6!__GI___libc_free(void * mem) (\build\glibc-CVJwZb\glibc-2.27\malloc\malloc.c:3134)
co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::_destruct_range<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, 0>(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > * p, size_t beg, size_t end) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:322)
co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::reset(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:134)
co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator>::~vector(co::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, co::default_allocator> * const this) (\home\cos\git\test-coost\libs\coost\include\co\vector.h:79)
Graph<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned int>::~Graph(Graph<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned int> * const this) 
[...]

Sorry for the lengthy description. Thanks for any advice

The text was updated successfully, but these errors were encountered:

piperoc · 2023-11-14T01:34:38Z

Just to make sure, I rewrote the graph class using std::vector and std::unorderded_map and I have no errors:

file: graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include "co/cout.h"
//#include "co/stl.h"
#include <vector>
#include <unordered_map>
#include "co/log.h"
#include "co/json.h"
#include "co/fastring.h"

using namespace std;

template <typename VertexType, typename IDType>
class Graph {

public:
    /// @brief default constructor
    Graph() = default;

    
    /// @brief add a vertex to the graph
    /// @param IdType the vertex id to be added
    /// @param VertexType the vertex to be added
    void addVertex(const IDType& id, const VertexType& vertex) {
        if (vertexMap.find(id) != vertexMap.end()) {
            ELOG << "vertex " << id << " already exists";
            return;
        }
        vertices.push_back(vertex);
        vertexMap[id] = vertices.size() - 1;
        adjacencyLists.push_back(vector<IDType>());
    }


    /// @brief add an edge to the graph
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    void addEdge(const IDType& source, const IDType& target) {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return;
        }
        adjacencyLists[vertexMap[source]].push_back(target);
    }

    /// @brief get a node by id
    /// @param IDType the vertex id
    /// @return VertexType the vertex
    VertexType findNode(const IDType& id) const {
        if (vertexMap.find(id) == vertexMap.end()) {
            ELOG << "vertex " << id << " does not exist";
            return VertexType();
        }
        return vertices[vertexMap.at(id)];
    }

    /// @brief remove a node by id
    /// @param IDType the vertex id
    void removeNode(const IDType& id) {
        if (vertexMap.find(id) == vertexMap.end()) {
            ELOG << "vertex " << id << " does not exist";
            return;
        }
        size_t index = vertexMap.at(id);
        vertices.erase(vertices.begin() + index);
        vertexMap.erase(id);
        adjacencyLists.erase(adjacencyLists.begin() + index);
        for (auto& list : adjacencyLists) {
            for (auto& node : list) {
                if (node == id) {
                    node = adjacencyLists.size();
                }
                if (node > index) {
                    node--;
                }
            }
        }
    }

    /// @brief remove an edge by id
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    void removeEdge(const IDType& source, const IDType& target) {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return;
        }
        size_t sourceIndex = vertexMap.at(source);
        size_t targetIndex = vertexMap.at(target);
        for (auto& node : adjacencyLists[sourceIndex]) {
            if (node == target) {
                node = adjacencyLists.size();
            }
            if (node > targetIndex) {
                node--;
            }
        }

        // remove the edge from the adjacency list
        adjacencyLists[sourceIndex].erase(
            std::remove(adjacencyLists[sourceIndex].begin(), adjacencyLists[sourceIndex].end(), adjacencyLists.size()),
            adjacencyLists[sourceIndex].end());

    }


    /// @brief VertexMap getter
    /// @return co::map<IDType, size_t> the vertex map
    unordered_map<IDType, size_t> VertexMap() const {
        return vertexMap;
    }

    /// @brief Vertices getter
    /// @return vector<VertexType> the vertices
    vector<VertexType> Vertices() const {
        return vertices;
    }

    /// @brief Edges getter
    /// @return vector<vector<IDType>> the adjacency lists
    vector<vector<IDType>> Edges() const {
        return adjacencyLists;
    }

    /// @brief function to check if an edge exists between two vertices
    /// @param IDType the source vertex id
    /// @param IDType the target vertex id
    /// @return bool true if the edge exists, false otherwise
    bool hasEdge(const IDType& source, const IDType& target) const {
        if (vertexMap.find(source) == vertexMap.end()) {
            ELOG << "vertex " << source << " does not exist";
            return false;
        }
        if (vertexMap.find(target) == vertexMap.end()) {
            ELOG << "vertex " << target << " does not exist";
            return false;
        }
        size_t sourceIndex = vertexMap.at(source);
        for (auto& node : adjacencyLists[sourceIndex]) {
            if (node == target) {
                return true;
            }
        }
        return false;
    }


private:
    /// @brief vertex list
    vector<VertexType> vertices;

    /// @brief vertex map
    unordered_map<IDType, size_t> vertexMap;

    /// @brief adjacency lists representing the graph
    vector<vector<IDType>> adjacencyLists;
};

#endif // GRAPH_H

maybe I should use something different that co::hash_map or learn how to use it correctly...

idealvin · 2023-11-14T05:14:30Z

Reproduced it. Let me see..

idealvin · 2023-11-14T10:25:54Z

@piperoc

sorry, a little busy at work these days.It is a bug in co::vector due to SSO of std::string. You may use fastring instead of std::string to avoid this problem first. I'll try to make a fix later.

piperoc · 2023-11-14T11:41:36Z

@idealvin awesome! That worked right away. Thank you so much for replying so quickly.

In case some needs it, here's the tests with the fastring instead of the std::string to get rid of the error:

file: graph.cc

#include "co/flag.h"
#include "co/cout.h"
#include "co/log.h"
#include "co/unitest.h"
#include "co/fastring.h"
#include "co/mem.h"
#include "co/graph.h"
#include <chrono>


namespace test {

DEF_test(graph) {

	Graph<fastring, uint32_t> myGraph = Graph<fastring, uint32_t>();

        myGraph.addVertex(1, "a");
        myGraph.addVertex(2, "b");
        myGraph.addVertex(3, "c");
        myGraph.addVertex(4, "d");

        myGraph.addEdge(1, 2);
        myGraph.addEdge(2, 3);
        myGraph.addEdge(3, 4);
        myGraph.addEdge(4, 1);
        myGraph.addEdge(2, 4);
        myGraph.addEdge(4, 2);

    DEF_case(check_vertices) {
		
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[1]],"a");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[2]],"b");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[3]],"c");
		EXPECT_EQ(myGraph.Vertices()[myGraph.VertexMap()[4]],"d");

    }

	DEF_case(find_node) {

		auto result = myGraph.findNode(3);
		EXPECT_EQ(result , "c");
	}

	DEF_case(find_node_not_found) {

		auto result = myGraph.findNode(5);
		EXPECT_EQ(result, "");
	}

	
	DEF_case(huge_graph) {
		
		const int NUMBER_OF_VERTICES = 2000;

		Graph<fastring, uint32_t> bigGraph;

		auto start = std::chrono::high_resolution_clock::now();

		for (int i = 0; i < NUMBER_OF_VERTICES; i++) {
			bigGraph.addVertex(i, "Vertex_" + std::to_string(i));
		}

		for (int sourceID = 1; sourceID <= NUMBER_OF_VERTICES; ++sourceID) {
			for (int targetID = 1; targetID <= NUMBER_OF_VERTICES; ++targetID) {
				// add 4 edges per vertex
                if (targetID  == (sourceID -1) || targetID == (sourceID +1) || targetID == (sourceID -2) || targetID == (sourceID +2)) 
						bigGraph.addEdge(sourceID, targetID);
			}
		}

		auto end = std::chrono::high_resolution_clock::now();
		auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

		cout << "Time taken to create the big graph: " << duration.count() << " microseconds" << std::endl;

		//EXPECT_EQ(bigGraph.Vertices().size(), NUMBER_OF_VERTICES);


		fastring halfwayVertex = "Vertex_" + std::to_string(NUMBER_OF_VERTICES/2);
		start = std::chrono::high_resolution_clock::now();
		auto result = bigGraph.findNode(NUMBER_OF_VERTICES/2);
		end = std::chrono::high_resolution_clock::now();
		duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
		cout << "Time taken to find node: " << duration.count() << " microseconds" << std::endl;
		EXPECT_EQ(result, halfwayVertex);

	}
    
}


} // namespace test

idealvin · 2023-11-15T04:21:03Z

@piperoc
Fixed in this commit.

piperoc · 2023-11-15T12:54:52Z

@idealvin that works. Thanks!

idealvin added the bug label Nov 14, 2023

idealvin added a commit that referenced this issue Nov 15, 2023

fix realloc in co::vector (#349)

ce8a4b1

idealvin closed this as completed Nov 30, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Memory allocation error using co/stl containers (co::vector, co::hash_map) #349

Memory allocation error using co/stl containers (co::vector, co::hash_map) #349

piperoc commented Nov 14, 2023

piperoc commented Nov 14, 2023

idealvin commented Nov 14, 2023

idealvin commented Nov 14, 2023

piperoc commented Nov 14, 2023

idealvin commented Nov 15, 2023

piperoc commented Nov 15, 2023

Memory allocation error using co/stl containers (co::vector, co::hash_map) #349

Memory allocation error using co/stl containers (co::vector, co::hash_map) #349

Comments

piperoc commented Nov 14, 2023

piperoc commented Nov 14, 2023

idealvin commented Nov 14, 2023

idealvin commented Nov 14, 2023

piperoc commented Nov 14, 2023

idealvin commented Nov 15, 2023

piperoc commented Nov 15, 2023