idealvin/coost

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

piperoc opened this issue · 6 comments

piperoc commented

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

piperoc commented

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 commented

Reproduced it. Let me see..

idealvin commented

@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 commented

@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
piperoc commented

@idealvin that works. Thanks!