It looks like you found a pretty nice approach there already.
A few general things stand out:
- Using globals
Magical constants and unsafe C-style arrays/raw pointers:
static vector<uint64_t> *movie_map = new vector<uint64_t>[1200000];
static vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000];
I'd suggest using std::vector again, because they can keep track of their own size, instead of using the same magic constants all over your code.
By the way, it looks like you should have used highest_actor and highest_movie there anyways
Mixing signed and unsigned integers in comparisons. In particular, in all the loops, use size_t (note your compiler should really warn you about these. Are you not using -Wall -Wextra -pedantic?)
- A lot of duplicated type identifiers. They lack expressiveness, and make it hard to see where bugs are (e.g. whether using
uint64_t vs int64_t was really on purpose)
- A lot of duplicated logic
- regarding the "hybrid" BFS state across movies and actors,
- as well as the backwards and forwards search state
- The loop inside BFS_OneLevel looks very suspicious: it's almost always an error to iterate a container under modification (in this case, items are being popped as well as pushed in the loop body). Only when I fully understood the code, I was able to work-out that the code was actually ok, but only because
i isn't actually used and Q_size reflects the number of items popped (from the front) while new items are always pushed at the end.
Use the standard library! This piece of code
if(!common_node.empty())
{
int64_t min=common_node[0];
for (long long i : common_node) {
if(i < min)
min= i;
}
/*int64_t nodecheck1=min; int64_t nodecheck2=min;
int flag=1;
while(flag!=0)
{
cout<<"Path starting from mid: "<<nodecheck1<<" "<<nodecheck2<<endl;
nodecheck1=f_prev_node[nodecheck1];
nodecheck2=b_prev_node[nodecheck2];
if(nodecheck1==start && nodecheck2 ==goalnode)
break;
}*/
return min;
}
really calls for standard library algorithm use:
if (!common_node.empty()) {
return *std::min_element(common_node.begin(), common_node.end());
}
A lot of the code makes assumptions about the validity of indices. In production code I would usually suggest replacing all of the container[idx] instances with the bounds-checking variants container.at(idx). Of course, good testing/review could remove the need, and since the objective here is to optimize the performance, I'd suggest to only keep the .at() style inside the parsing - because it's better to fail early than to continue with Undefined Behaviour in case the hard-coded capacities don't suffice.
While cleaning up the code (remove globals, duplication, unused code, bad naming) and running some benchmarks using the supplied input file, I found:
- A bug in your line 97 (the
&& should be ||); your code might never complete, for some inputs
- The birectional search does not in practice improve the speed (note; worst-case behaviour will be improved, but at the cost of complexity)
boost::small_vector yields significant speed up (on average, there are <=10 relations per vertex) Destructing the maps takes significant time.
This is one of those rare occasions where I'd suggest purposefully leaking the memory since you know the program will be terminating anyways.
Exposition Of Cleaned Up Code
Taking the above suggestions to heart, I'd start by cutting unneeded headers:
#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
Introducing some useful, expressive, typedefs:
using Id = uint64_t;
using Distance = int64_t;
using Ids = std::vector<Id>;
using Adjacency = std::vector<Ids>;
Later, it will be easy to replace any of these like e.g.
using Ids = boost::container::small_vector<Id, 10>;
Grouping your data with the logic, e.g.:
class Data {
private:
Adjacency movie_map { 1200000 },
actor_map { 2000000 };
using ColorMap = std::vector<bool>;
using Queue = std::deque<Id>;
struct BFS_State;
public:
explicit Data(std::string const& fname) { Parse(fname); }
Distance BFS(Id start, Id goalnode) const;
Distance BidiBFS(Id start, Id goalnode) const;
private:
bool BF_Step(BFS_State& state) const;
bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const;
void Parse(std::string const& fname);
};
Note that I added BFS in addition to BidiBFS because I think it's worth considering the increased complexity of the bidirectional algorithm vs. the effective performance gain
The BFS State
I've defined this as simply the "grouping" of things you have prefixed in b_* and f_* flavours.
struct BFS_State {
BFS_State(size_t actors, size_t movies)
: visited_act(actors),
visited_mov(movies),
dist(actors, 0)
{ }
Queue queue;
ColorMap visited_act, visited_mov;
std::vector<Distance> dist;
bool Enqueue(Id actor, Distance distance = 0) {
if (visited_act[actor])
return false;
visited_act[actor] = true;
queue.push_back(actor);
dist[actor] = distance;
return true;
}
};
The algorithm kernel can now look much simpler:
Distance BidiBFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State
forward { actor_map.size(), movie_map.size() },
back { actor_map.size(), movie_map.size() };
forward.Enqueue(start);
back.Enqueue(goalnode);
while (BF_Step(forward) || BF_Step(back)) {
std::vector<Distance> common_node;
for (Id i = 0; i < actor_map.size(); ++i) {
if (back.visited_act[i] && forward.visited_act[i]) {
common_node.push_back(forward.dist[i] + back.dist[i]);
}
}
if (!common_node.empty()) {
return *std::min_element(common_node.begin(), common_node.end());
}
}
return -1;
}
Note this is still basically exactly the same algorithm (modulo the bug you had in the while condition), but it is now much clearer what is happening, and why.
Note that I moved the logic to check for previously-visited actors inside Enqueue to avoid duplicating that logic: when reviewing your code I had to think really hard whether this block of code was actually necessary/correct:
std::queue<uint64_t> f_Q;
std::queue<uint64_t> b_Q;
f_Q.push(start); //push starting actor in queue
b_Q.push(goalnode); //push starting actor in queue
//cout << "Alive" << endl;
f_visited_act[start] = true;
b_visited_act[goalnode] = true;
BF_Step
BF_Step is basically your BFS_OneLevel method, but
- it addresses the iffy loop over a mutating queue
it returns true or false to indicate whether all queued nodes have been processed, so you can simply write
while (BF_Step(fwd) || BF_Step(bck)) {
without "knowing" about the implementation specifics of the queue.
Here it is:
bool BF_Step(BFS_State& state) const {
if (state.queue.empty())
return false;
Queue local_queue;
std::swap(local_queue, state.queue);
BF_Visit(local_queue, state);
return true;
}
As you can see, we made the intent of the loop clear: we swap the contents of the queue with an empty one. We then loop over all previously queued nodes (the local_queue). At the end of the step there might be new queued items, but none of the originally queued nodes will be.
If there weren't any items to begin with, we return false.
BF_Visit
What happened here? I extracted the logic that was in the BFS_OneLevel loop. I will admit I only did this after implementing a non-bidirectional version of the BF search. The BF_Visit looks like your original code:
bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
// note that `nodes` can alias `state.queue` if it's not a bidirectional search
// returns true if goalnode reached (not used for bidi search)
while (!nodes.empty()) {
Id top = nodes.front();
nodes.pop_front();
if (top == goalnode)
return true;
for (Id movie : actor_map[top]) {
if (state.visited_mov[movie]) continue;
state.visited_mov[movie] = true;
for (Id actor : movie_map[movie]) {
state.Enqueue(actor, state.dist[top] + 1);
}
}
}
return false;
}
The subtle differences are:
- it optionally terminates early when a
goalnode is reached (this is useful in the single-direction BFS)
- It uses potentially seperate queus for pushing vs. iterating. This means that when
BF_Step calls it, it can visit the local_queue nodes, but when BFS calls it, it may just continue until no more nodes get pushed (and the queue is drained).
BFS - Bonus
To complete the picture, here's how a uni-directional BFS looks based on the same building blocks (BFS_State, BF_Visit):
Distance BFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State state { actor_map.size(), movie_map.size() };
state.Enqueue(start);
if (BF_Visit(state.queue, state, goalnode))
return state.dist[goalnode];
return -1;
}
That's pretty elegant!
Data::Parse - style only
This is basically your code, but
- using a lamda to reduce duplicated code and increase legibility
- using
.at(i) instead of the unchecked [i] indexing
void Parse(std::string const& fname) {
std::ifstream file(fname);
auto skip_to = [&file](char ch) -> std::istream& {
return file.ignore(std::numeric_limits<std::streamsize>::max(), ch);
};
skip_to('\n');
Id fir, sec;
while (file >> fir && skip_to(',') && file >> sec) {
movie_map.at(sec).push_back(fir);
actor_map.at(fir).push_back(sec);
}
}
main - style only
Little has changed, though
- I did notice that exiting the program could take up to 0.8 seconds, so I made
Data instance leaked on purpose
- You can now easily choose between
BidiBFS and BFS
int main() {
std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));
std::vector<std::future<Distance> > queries;
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));
for (auto& result : queries) {
std::cout << "Ans: " << result.get() << std::endl;
}
data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
if (data) timed("Destruct data", [&data] { data.reset(); });
}
The timed facility is a really simple general purpose wrapper:
#include <chrono>
template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }
template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
using C = std::chrono::high_resolution_clock;
static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);
auto s = C::now();
auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });
return f();
}
Note It does what you expect it does, but it's a bit out of scope for this review. Note that it does weigh an additional 14 Lines Of Code, so in effect my cleaned up code is considerably shorter than the question code, even though it has more features and has become more readable.
PERFORMANCE ASSESSMENT #1
At this point, the code looks like this:
Live On Coliru
#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <boost/container/small_vector.hpp>
using Id = uint64_t;
using Distance = int64_t;
using Ids = boost::container::small_vector<Id, 10>; // std::vector<Id>;
using Adjacency = std::vector<Ids>;
class Data {
private:
Adjacency movie_map { 1200000 },
actor_map { 2000000 };
using ColorMap = std::vector<bool>;
using Queue = std::deque<Id>;
struct BFS_State {
BFS_State(size_t actors, size_t movies)
: visited_act(actors),
visited_mov(movies),
dist(actors, 0)
{ }
Queue queue;
ColorMap visited_act, visited_mov;
std::vector<Distance> dist;
bool Enqueue(Id actor, Distance distance = 0) {
if (visited_act[actor])
return false;
visited_act[actor] = true;
queue.push_back(actor);
dist[actor] = distance;
return true;
}
};
public:
explicit Data(std::string const& fname) { Parse(fname); }
Distance BFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State state { actor_map.size(), movie_map.size() };
state.Enqueue(start);
if (BF_Visit(state.queue, state, goalnode))
return state.dist[goalnode];
return -1;
}
Distance BidiBFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State
fwd { actor_map.size(), movie_map.size() },
bck { actor_map.size(), movie_map.size() };
fwd.Enqueue(start);
bck.Enqueue(goalnode);
while (BF_Step(fwd) || BF_Step(bck)) {
std::vector<Distance> common_node;
for (Id i = 0; i < actor_map.size(); ++i) {
if (bck.visited_act[i] && fwd.visited_act[i]) {
common_node.push_back(fwd.dist[i] + bck.dist[i]);
}
}
if (!common_node.empty()) {
return *std::min_element(common_node.begin(), common_node.end());
}
}
return -1;
}
private:
bool BF_Step(BFS_State& state) const {
if (state.queue.empty())
return false;
Queue local_queue;
std::swap(local_queue, state.queue);
BF_Visit(local_queue, state);
return true;
}
bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
// note that `nodes` can alias `state.queue` if it's not a bidirectional search
// returns true if goalnode reached (not used for bidi search)
while (!nodes.empty()) {
Id top = nodes.front();
nodes.pop_front();
if (top == goalnode)
return true;
for (Id movie : actor_map[top]) {
if (state.visited_mov[movie]) continue;
state.visited_mov[movie] = true;
for (Id actor : movie_map[movie]) {
state.Enqueue(actor, state.dist[top] + 1);
}
}
}
return false;
}
void Parse(std::string const& fname) {
std::ifstream file(fname);
auto skip_to = [&file](char ch) -> std::istream& {
return file.ignore(std::numeric_limits<std::streamsize>::max(), ch);
};
skip_to('\n');
Id fir, sec;
while (file >> fir && skip_to(',') && file >> sec) {
movie_map.at(sec).push_back(fir);
actor_map.at(fir).push_back(sec);
}
}
};
#include <chrono>
#include <memory>
template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }
template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
using C = std::chrono::high_resolution_clock;
static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);
auto s = C::now();
auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });
return f();
}
int main() {
std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));
std::vector<std::future<Distance> > queries;
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));
for (auto& result : queries) {
std::cout << "Ans: " << result.get() << std::endl;
}
data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
if (data) timed("Destruct data", [&data] { data.reset(); });
}
The timings for your test case are now:
Movie map created: 4087.69ms
Ans: 4
Ans: 3
real 0m4.431s
user 0m4.352s
sys 0m0.184s
The original timings on my system were nearly identical to yours (5.9s). That's a 25% performance increase. Not bad
OPTIMIZING
Two optimizations applied:
Using small_vector for the adjacency containers
Because many actors will have played in < 10 movies, it may make sense to cut down on memory allocation costs there. small_vector is a nice candidate as it gracefully degrades to allocating behaviour if required.
using Ids = boost::container::small_vector<Id, 10>;
Using Memory Mapped Files And Spirit
Taking the approach from my answer over at [SO]: https://stackoverflow.com/questions/48525833/how-to-parse-csv-in-c-using-boost-memory-maps/48533015#48533015 I changed the implementation of Data::Parse into the equivalent:
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
void Data::Parse(std::string const& fname) {
boost::iostreams::mapped_file_source mfs(fname);
struct Handler {
Data* _this;
void operator()(uint64_t fir, uint64_t sec) const {
_this->movie_map.at(sec).push_back(fir);
_this->actor_map.at(fir).push_back(sec);
}
};
boost::phoenix::function<Handler> handle { Handler{this} };
using namespace boost::spirit::qi;
if (!phrase_parse(mfs.begin(), mfs.end(),
*(char_ - eol) >> eol >> (uint_ >> ',' >> uint_)[handle(_1, _2)] % eol, blank))
{
throw std::runtime_error("Parse failed\n");
}
}
Note that qi::phrase_parse with qi::blank as a skipper makes it so that whitespace is ignored (like your istream code did).
PERFORMANCE ASSESSMENT #2
This indeed slashes the runtime further:
Movie map created: 1456.61ms
Ans: 4
Ans: 3
real 0m1.790s
user 0m1.772s
sys 0m0.116s
That's a net improvement of 70% overall. Not bad :) The final code looks like this:
Live On Coliru
#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <boost/container/small_vector.hpp>
using Id = uint64_t;
using Distance = int64_t;
using Ids = boost::container::small_vector<Id, 10>; // std::vector<Id>;
using Adjacency = std::vector<Ids>;
class Data {
private:
Adjacency movie_map { 1200000 },
actor_map { 2000000 };
using ColorMap = std::vector<bool>;
using Queue = std::deque<Id>;
struct BFS_State {
BFS_State(size_t actors, size_t movies)
: visited_act(actors),
visited_mov(movies),
dist(actors, 0)
{ }
Queue queue;
ColorMap visited_act, visited_mov;
std::vector<Distance> dist;
bool Enqueue(Id actor, Distance distance = 0) {
if (visited_act[actor])
return false;
visited_act[actor] = true;
queue.push_back(actor);
dist[actor] = distance;
return true;
}
};
public:
explicit Data(std::string const& fname) { Parse(fname); }
Distance BFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State state { actor_map.size(), movie_map.size() };
state.Enqueue(start);
if (BF_Visit(state.queue, state, goalnode))
return state.dist[goalnode];
return -1;
}
Distance BidiBFS(Id start, Id goalnode) const {
if (start == goalnode)
return 0;
BFS_State
fwd { actor_map.size(), movie_map.size() },
bck { actor_map.size(), movie_map.size() };
fwd.Enqueue(start);
bck.Enqueue(goalnode);
while (BF_Step(fwd) || BF_Step(bck)) {
std::vector<Distance> common_node;
for (Id i = 0; i < actor_map.size(); ++i) {
if (bck.visited_act[i] && fwd.visited_act[i]) {
common_node.push_back(fwd.dist[i] + bck.dist[i]);
}
}
if (!common_node.empty()) {
return *std::min_element(common_node.begin(), common_node.end());
}
}
return -1;
}
private:
bool BF_Step(BFS_State& state) const {
if (state.queue.empty())
return false;
Queue local_queue;
std::swap(local_queue, state.queue);
BF_Visit(local_queue, state);
return true;
}
bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
// note that `nodes` can alias `state.queue` if it's not a bidirectional search
// returns true if goalnode reached (not used for bidi search)
while (!nodes.empty()) {
Id top = nodes.front();
nodes.pop_front();
if (top == goalnode)
return true;
for (Id movie : actor_map[top]) {
if (state.visited_mov[movie]) continue;
state.visited_mov[movie] = true;
for (Id actor : movie_map[movie]) {
state.Enqueue(actor, state.dist[top] + 1);
}
}
}
return false;
}
void Parse(std::string const& fname);
};
#include <chrono>
#include <memory>
template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }
template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
using C = std::chrono::high_resolution_clock;
static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);
auto s = C::now();
auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });
return f();
}
int main() {
std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));
std::vector<std::future<Distance> > queries;
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));
for (auto& result : queries) {
std::cout << "Ans: " << result.get() << std::endl;
}
data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
if (data) timed("Destruct data", [&data] { data.reset(); });
}
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
void Data::Parse(std::string const& fname) {
boost::iostreams::mapped_file_source mfs(fname);
struct Handler {
Data* _this;
void operator()(uint64_t fir, uint64_t sec) const {
_this->movie_map.at(sec).push_back(fir);
_this->actor_map.at(fir).push_back(sec);
}
};
boost::phoenix::function<Handler> handle { Handler{this} };
using namespace boost::spirit::qi;
if (!phrase_parse(mfs.begin(), mfs.end(),
*(char_ - eol) >> eol >> (uint_ >> ',' >> uint_)[handle(_1, _2)] % eol, blank))
{
throw std::runtime_error("Parse failed\n");
}
}
