Comparação de Resultados & Análise de Desempenho
Com o código pronto e inputs e outputs gerados, conseguimos aplicar a ferramenta valgrind
em todo o código para verificar se há algum erro de memória e para realizar o profiling do código.
Erros e Gerenciamento Memória
O Valgrind é uma ferramenta que permite verificar se há erros de memória no código, como por exemplo, acessos a memória não alocada, acesso a memória já liberada, uso de memória não inicializada, etc. Além disso, ele também permite realizar o profiling do código, ou seja, verificar o tempo de execução de cada função e o consumo de memória de cada função.
Para utilizar o Valgrind, basta executar o comando abaixo:
valgrind -s --leak-check=full --track-origins=yes ./bin/main 0 < ./in/input_300.txtConfira o output abaixo:
---->GREEDY:==162893== Memcheck, a memory error detector==162893== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.==162893== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info==162893== Command: ../bin/main 0==162893== 0 4000 100 22 0.00196802==162893== ==162893== HEAP SUMMARY:==162893== in use at exit: 0 bytes in 0 blocks==162893== total heap usage: 4,012 allocs, 4,012 frees, 142,448 bytes allocated==162893== ==162893== All heap blocks were freed -- no leaks are possible==162893== ==162893== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)---->RANDOM:==162996== Memcheck, a memory error detector==162996== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.==162996== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info==162996== Command: ../bin/main 1==162996== 0 4000 100 10 0.0162485==162996== ==162996== HEAP SUMMARY:==162996== in use at exit: 0 bytes in 0 blocks==162996== total heap usage: 4,904 allocs, 4,904 frees, 173,756 bytes allocated==162996== ==162996== All heap blocks were freed -- no leaks are possible==162996== ==162996== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)Dos dois algoritmos implementados, ambos (greedy e o random) não apresentaram nenhum erro de memória.
Profiling
O profiling é uma técnica que permite verificar o tempo de execução de cada função e o consumo de memória de cada função.
Para realizar o profiling, basta executar o comando abaixo:
valgrind --tool=callgrind ./bin/main 0 < ./in/input_300.txtcallgrind_annotate callgrind.out.X scheduler.cppcallgrind_annotate callgrind.out.X greedy.cppcallgrind_annotate callgrind.out.X random.cppConfira o output para os arquivos greedy.cpp e scheduler.cpprespectivamente:
---------------------------------------------------------------------------------- User-annotated source: greedy.cpp--------------------------------------------------------------------------------Ir . #include "greedy.hpp" . . void Greedy::scheduleMovies() 4 { 13 int *i = new int(-1);237,827 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (1x) 7 while (++*i < *this->movies)2,870 if (this->movieIsValid(this->moviesList[*i]))229,295 => greedy.cpp:Greedy::scheduleMovies()'2 (1x)3,359 => /home/parallels/Documents/insper/7o/supercomp/project/lib/scheduler/scheduler.cpp:Scheduler::movieIsValid(Movie*) (167x)1,446 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (2x) . this->addMovieToAgenda(this->moviesList[*i]); . delete i; . } 5 <counts for unidentified lines in greedy.cpp>--------------------------------------------------------------------------------Ir --------------------------------------------------------------------------------2,894 events annotated---------------------------------------------------------------------------------- User-annotated source: scheduler.cpp--------------------------------------------------------------------------------Ir . #include "scheduler.hpp" . #include <algorithm> . #include <iostream> . 4 Scheduler::Scheduler() . { 13 this->movies = new int; 3,258 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (1x) 7 this->categories = new int; 2,395 => ???:operator new(unsigned long)'2 (1x) . 12 this->acceptedMovies = new Movie *[24]; 2,168 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (1x) 9 this->acceptedMoviesCount = new int(-1); 670 => ???:operator new(unsigned long)'2 (1x) 9 this->agendaBitset = new std::bitset<24>; 445 => ???:operator new(unsigned long)'2 (1x) 7 this->movieScheduleBitset = new std::bitset<24>; 221 => ???:operator new(unsigned long)'2 (1x) . . this->moviesList = nullptr; 1 this->maxMoviesPerCat = nullptr; 3 } . 5 Scheduler::~Scheduler() . { 23 for (int i = 0; i < *this->movies; i++)55,999 delete this->moviesList[i];566,136 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (1x) . delete[] this->moviesList; . 10 delete this->movies; 127 => ???:operator delete(void*, unsigned long)'2 (1x) 627 => scheduler.cpp:Scheduler::~Scheduler()'2 (1x) 15 delete this->categories; 485 => ???:operator delete[](void*)'2 (1x) 127 => ???:operator delete(void*, unsigned long)'2 (1x) . delete[] this->maxMoviesPerCat; 7 delete[] this->acceptedMovies; 377 => ???:operator delete[](void*)'2 (1x) . 22 delete this->acceptedMoviesCount; 254 => ???:operator delete(void*, unsigned long)'2 (2x) . delete this->agendaBitset; . delete this->movieScheduleBitset; . } . . void Scheduler::readMoviesCatalog() 11 { 20 std::cin >> *this->movies >> *this->categories;16,494,085 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (1x) 12 this->maxMoviesPerCat = new int[*this->categories];16,484,102 => ???:operator new[](unsigned long) (1x) 12 this->moviesList = new Movie *[*this->movies];16,483,873 => ???:operator new[](unsigned long)'2 (1x) . . int i = -1; 506 while (++i < *this->categories) 800 std::cin >> this->maxMoviesPerCat[i];16,483,649 => ???:std::istream::operator>>(int&)'2 (1x) . . i = -1; . int cat; . short int startTime, endTime;16,007 while (++i < *this->movies) . {76,010 std::cin >> startTime >> endTime >> cat;33,841,683,144 => ???:std::istream::operator>>(short&)'2 (3,999x)32,000 this->moviesList[i] = new Movie;33,843,201,080 => ???:operator new(unsigned long)'2 (4,000x)20,000 this->moviesList[i]->category = cat; 8,000 this->moviesList[i]->startTime = startTime; 8,000 this->moviesList[i]->endTime = endTime; . } 2 std::sort(this->moviesList, this->moviesList + *this->movies, [](Movie *a, Movie *b) {89,378 if (a->endTime == b->endTime)88,546 return a->startTime < b->startTime;21,369 return a->endTime < b->endTime; . }); 11 } . . void Scheduler::showVars() . { . std::cout << "Movies: " << *this->movies << '\n'; . std::cout << "Categories: " << *this->categories << '\n'; . std::cout << "Max Movies Per Category: " << '\n'; . for (int i = 0; i < *this->categories; i++) . std::cout << this->maxMoviesPerCat[i] << ' '; . std::cout << '\n'; . std::cout << "Movies List: " << '\n'; . for (int i = 0; i < *this->movies; i++) . std::cout << this->moviesList[i]->startTime << ' ' << this->moviesList[i]->endTime << ' ' << this->moviesList[i]->category << '\n'; . } . . bool Scheduler::movieIsValid(Movie *movie) 4,000 { 4,000 this->movieScheduleBitset->reset();47,152 for (short j = movie->startTime; j < movie->endTime; j++)10,384 this->movieScheduleBitset->set(j); . . if ((!(*this->movieScheduleBitset & *this->agendaBitset).any() && 9,086 this->maxMoviesPerCat[movie->category - 1] > 0) && 4,160 (movie->startTime < movie->endTime && movie->startTime >= 0 && movie->endTime < 24)) . return 1; . 3,503 return 0; 4,000 } . . void Scheduler::addMovieToAgenda(Movie *movie) . { 115 if (!(*this->movieScheduleBitset & *this->agendaBitset).any() && 92 this->maxMoviesPerCat[movie->category - 1] > 0) . { . *this->agendaBitset |= *this->movieScheduleBitset; 138 this->acceptedMovies[++*this->acceptedMoviesCount] = movie; 115 --this->maxMoviesPerCat[movie->category - 1]; . } 23 } . . void Scheduler::showAcceptedMovies() . { . std::sort(this->acceptedMovies, this->acceptedMovies + *this->acceptedMoviesCount, [](Movie *a, Movie *b) { . if (a->endTime == b->endTime) . return a->startTime < b->startTime; . return a->endTime < b->endTime; . }); . for (int i = 0; i <= *this->acceptedMoviesCount; i++) . std::cout << this->acceptedMovies[i]->startTime << ' ' << this->acceptedMovies[i]->endTime << ' ' << this->acceptedMovies[i]->category << '\n'; 3 } 9 <counts for unidentified lines in scheduler.cpp>--------------------------------------------------------------------------------Ir --------------------------------------------------------------------------------503,601 events annotatedAo analisar o resultado acima, podemos dizer que a função que realiza a maior parte do processamento
(entre bool Scheduler::movieIsValid(Movie *movie) e void Scheduler::addMovieToAgenda(Movie *movie)) é
a movieIsValid, que é chamada 4.000 vezes. A função addMovieToAgenda é chamada 23 vezes. que é esperado.
Um jeito de melhorar esses números seria otmizar o código suficientemente para que as checagens de validade de filmes sejam feitas menos vezes. Isso pode ser feito, por exemplo, ao invés de checar se o filme é válido para cada filme da lista, checar se o filme é válido para cada horário do dia, e então adicionar os filmes válidos para cada horário do dia em uma lista.
Confira o output para os arquivosrandom.cpp e scheduler.cpp respectivamente:
---------------------------------------------------------------------------------- User-annotated source: random.cpp--------------------------------------------------------------------------------Ir -- line 2 ---------------------------------------- . #include <cstdlib> . #include <ctime> . #include <algorithm> . #include <unordered_set> . #include <vector> . #include <iostream> . . void Random::scheduleMovies() 10 { 22 std::srand(30);1,325,383 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (2x) . 2 std::unordered_set<int> *visitedIndexes = new std::unordered_set<int>(); 9 std::unordered_set<int> *randomChecker = new std::unordered_set<int>();1,313,984 => ???:operator new(unsigned long)'2 (1x) 11 int *i = new int(-1);1,313,754 => ???:operator new(unsigned long)'2 (1x) 8 int *choosenIndex = new int;1,313,530 => ???:operator new(unsigned long)'2 (1x) . 7,874 while (++*i < *this->movies && this->agendaBitset->count() < 24) . {153,830 if (std::rand() % 100 < 75)1,309,695 => /usr/include/c++/9/bits/hashtable.h:std::pair<std::__detail::_Node_iterator<int, true, false>, bool> std::_Hashtable<int, int, std::allocator<int>, std::__detail::_Identity, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, true, true> >::_M_insert<int const&, std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<int, false> > > >(int const&, std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<int, false> > > const&, std::integral_constant<bool, true>, unsigned long) [clone .constprop.0] (1x) 2,277 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (3x) 783 => /build/glibc-RIFKjK/glibc-2.31/stdlib/rand.c:rand (9x) 197 => /home/parallels/Documents/insper/7o/supercomp/project/lib/scheduler/scheduler.cpp:Scheduler::movieIsValid(Movie*) (8x) . { 972 if (this->movieIsValid(this->moviesList[*i]) && visitedIndexes->count(*i) == 0) . { . this->addMovieToAgenda(this->moviesList[*i]); . visitedIndexes->insert(*i); . } . } . else . { . *choosenIndex = std::rand() % *this->movies;-- line 30 ------------------------------------------ line 33 ---------------------------------------- . if (this->movieIsValid(this->moviesList[*choosenIndex])) . { . this->addMovieToAgenda(this->moviesList[*choosenIndex]); . visitedIndexes->insert(*choosenIndex); . break; . } . *choosenIndex = std::rand() % *this->movies; . visitedIndexes->insert(*choosenIndex); 531 } while (visitedIndexes->count(*choosenIndex) == 0 && this->agendaBitset->count() > 0); . } . } . . delete choosenIndex; 7 delete visitedIndexes; 244 => ???:operator delete(void*, unsigned long)'2 (1x) . delete randomChecker; 3 delete i; 12 } 9 <counts for unidentified lines in random.cpp>--------------------------------------------------------------------------------Ir --------------------------------------------------------------------------------163,291 events annotated---------------------------------------------------------------------------------- User-annotated source: scheduler.cpp--------------------------------------------------------------------------------Ir . #include "scheduler.hpp" . #include <algorithm> . #include <iostream> . 4 Scheduler::Scheduler() . { 13 this->movies = new int; 3,258 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (1x) 7 this->categories = new int; 2,395 => ???:operator new(unsigned long)'2 (1x) . 12 this->acceptedMovies = new Movie *[24]; 2,168 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (1x) 9 this->acceptedMoviesCount = new int(-1); 670 => ???:operator new(unsigned long)'2 (1x) 9 this->agendaBitset = new std::bitset<24>; 445 => ???:operator new(unsigned long)'2 (1x) 7 this->movieScheduleBitset = new std::bitset<24>; 221 => ???:operator new(unsigned long)'2 (1x) . . this->moviesList = nullptr; 1 this->maxMoviesPerCat = nullptr; 3 } . 5 Scheduler::~Scheduler() . { 5 for (int i = 0; i < *this->movies; i++)56,017 delete this->moviesList[i];507,873 => ???:operator delete(void*, unsigned long) (3,999x) 2,415 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (2x) . delete[] this->moviesList; . 10 delete this->movies; 627 => scheduler.cpp:Scheduler::~Scheduler()'2 (1x) 127 => ???:operator delete(void*, unsigned long) (1x) 15 delete this->categories; 485 => ???:operator delete[](void*)'2 (1x) 127 => ???:operator delete(void*, unsigned long) (1x) . delete[] this->maxMoviesPerCat; 7 delete[] this->acceptedMovies; 377 => ???:operator delete[](void*)'2 (1x) . 22 delete this->acceptedMoviesCount; 254 => ???:operator delete(void*, unsigned long) (2x) . delete this->agendaBitset; . delete this->movieScheduleBitset; . } . . void Scheduler::readMoviesCatalog() 11 { 20 std::cin >> *this->movies >> *this->categories;16,494,077 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve (1x) 12 this->maxMoviesPerCat = new int[*this->categories];16,484,094 => ???:operator new[](unsigned long) (1x) 12 this->moviesList = new Movie *[*this->movies];16,483,865 => ???:operator new[](unsigned long)'2 (1x) . . int i = -1; 506 while (++i < *this->categories) 800 std::cin >> this->maxMoviesPerCat[i];1,625,486,118 => ???:std::istream::operator>>(int&)'2 (99x) . . i = -1; . int cat; . short int startTime, endTime;16,007 while (++i < *this->movies) . {76,010 std::cin >> startTime >> endTime >> cat;16,353,967 => /build/glibc-RIFKjK/glibc-2.31/elf/../sysdeps/aarch64/dl-trampoline.S:_dl_runtime_resolve'2 (1x)32,000 this->moviesList[i] = new Movie;33,843,181,942 => ???:operator new(unsigned long)'2 (4,000x)20,000 this->moviesList[i]->category = cat; 8,000 this->moviesList[i]->startTime = startTime; 8,000 this->moviesList[i]->endTime = endTime; . } 2 std::sort(this->moviesList, this->moviesList + *this->movies, [](Movie *a, Movie *b) {89,378 if (a->endTime == b->endTime)88,546 return a->startTime < b->startTime;21,369 return a->endTime < b->endTime; . }); 11 } . . void Scheduler::showVars() . { . std::cout << "Movies: " << *this->movies << '\n'; . std::cout << "Categories: " << *this->categories << '\n'; . std::cout << "Max Movies Per Category: " << '\n'; . for (int i = 0; i < *this->categories; i++) . std::cout << this->maxMoviesPerCat[i] << ' '; . std::cout << '\n'; . std::cout << "Movies List: " << '\n'; . for (int i = 0; i < *this->movies; i++) . std::cout << this->moviesList[i]->startTime << ' ' << this->moviesList[i]->endTime << ' ' << this->moviesList[i]->category << '\n'; . } . . bool Scheduler::movieIsValid(Movie *movie) 4,000 { 4,000 this->movieScheduleBitset->reset();47,116 for (short j = movie->startTime; j < movie->endTime; j++)10,372 this->movieScheduleBitset->set(j); . . if ((!(*this->movieScheduleBitset & *this->agendaBitset).any() && 9,048 this->maxMoviesPerCat[movie->category - 1] > 0) && 4,104 (movie->startTime < movie->endTime && movie->startTime >= 0 && movie->endTime < 24)) . return 1; . 3,498 return 0; 4,000 } . . void Scheduler::addMovieToAgenda(Movie *movie) . { 55 if (!(*this->movieScheduleBitset & *this->agendaBitset).any() && 44 this->maxMoviesPerCat[movie->category - 1] > 0) . { . *this->agendaBitset |= *this->movieScheduleBitset; 66 this->acceptedMovies[++*this->acceptedMoviesCount] = movie; 55 --this->maxMoviesPerCat[movie->category - 1]; . } 11 } . . void Scheduler::showAcceptedMovies() . { . std::sort(this->acceptedMovies, this->acceptedMovies + *this->acceptedMoviesCount, [](Movie *a, Movie *b) { . if (a->endTime == b->endTime) . return a->startTime < b->startTime; . return a->endTime < b->endTime; . }); . for (int i = 0; i <= *this->acceptedMoviesCount; i++) . std::cout << this->acceptedMovies[i]->startTime << ' ' << this->acceptedMovies[i]->endTime << ' ' << this->acceptedMovies[i]->category << '\n'; 3 } 9 <counts for unidentified lines in scheduler.cpp>--------------------------------------------------------------------------------Ir --------------------------------------------------------------------------------503,202 events annotatedAo analisar o resultado acima (entre bool Scheduler::movieIsValid(Movie *movie) e void Scheduler::addMovieToAgenda(Movie *movie))
podemos ver que a função movieIsValid é chamado 4.000 vezes, enquanto a função addMovieToAgenda é chamado 55 vezes.
Isso significa que para 32 filmes a checagem está falhando e é feita a tentativa de adicionar o filme na agenda.
Está adição irá falhar graças à checagem feita na função addMovieToAgenda, mas mesmo assim o programa irá tentar adicionar o filme na agenda.
Para resolver esse problema, é necessário rever o código para que não haja a tentativa de adicionar um filme inválido ou repetido na agenda, já que
os índices gerados pelo rand() são aleatórios, não podemos garantir que o número aleatorizado já não foi utilizado anteriormente.
Gráficos de desempenho
Para medir o desempenho do programa, geramos uma serie de gráficos diferentes que buscam análisar o desempenho do programa em diferentes cenários.
O número máximo de filmes está como 22 por conta de termos utilizado o índice máximo de filmes escolhidos dentro de sua lista (0 a 22), e não a sua soma.
filmes assistidos X total de filmes (número de categorias fixo)

Do gráfico acima podemos ver que para grandes quantidades de filmes, a probabilidade da heurística gulosa conseguir completar a agenda é muito grande, já que os arquivos de inputs gerados têm pelo menos 1000 filmes. Já no caso da heurística gulosa com a aleatorização, dada a chance de escolher um filme aleatório, a probabilidade de conseguir completar a agenda é muito menor.
filmes assistidos X total de categorias (número de filmes fixo)

Do mesmo modo que o gráfico anterior, podemos ver que para grandes quantidades de filmes, a probabilidade da heurística gulosa conseguir completar a agenda é muito grande, já que os arquivos de inputs gerados têm pelo menos 1000 filmes. Já no caso da heurística gulosa com a aleatorização, a quantidade de categorias não influencia muito na probabilidade de conseguir completar a agenda.
runtime X total de filmes (número de categorias fixo)

Podemos observar que ao aumentar o número de filmes, o tempo de execução do programa tende a aumentar, isso é esperado, já que o programa precisa analisar mais filmes para encontrar uma solução.
runtime X total de categorias (número de filmes fixo)

No caso de ter o número de filmes e variar o número de categorias, podemos ver que o tempo de execução do programa tende a permanecer constante, isso é esperado, já que o número de categorias não influencia muito no tempo de execução do programa.