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.txt
👀

Confira 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.txt
callgrind_annotate callgrind.out.X scheduler.cpp
callgrind_annotate callgrind.out.X greedy.cpp
callgrind_annotate callgrind.out.X random.cpp
👀

Confira 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 annotated

Ao 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 annotated

Ao 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)

assistidos_vs_total

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)

assistidos_vs_categorias

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)

runtime_vs_total

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)

runtime_vs_categorias

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.