35
edits
Changes
Created page with "= Thunderbird = == Team Members == # [mailto:ksanghun@myseneca.ca?subject=GPU610 Sanghun Kim] # [mailto:hpark77@myseneca.ca?subject=GPU610 Heetai Park] # [mailto:wlee64@mysene..."
= Thunderbird =
== Team Members ==
# [mailto:ksanghun@myseneca.ca?subject=GPU610 Sanghun Kim]
# [mailto:hpark77@myseneca.ca?subject=GPU610 Heetai Park]
# [mailto:wlee64@myseneca.ca?subject=GPU610 Wonho Lee]
# [mailto:ksanghun@myseneca.ca?subject=GPU610,hpark77@myseneca.ca?subject=GPU610,wlee64@myseneca.ca?subject=GPU610 eMail All]
== Progress ==
=== Assignment 1 ===
==== Profiling: LZW algorithm ====
It's a simple version of LZW compression algorithm with 12 bit codes.
void compress(string input, int size, string filename) {
unordered_map<string, int> compress_dictionary(MAX_DEF);
//Dictionary initializing with ASCII
for ( int unsigned i = 0 ; i < 256 ; i++ ){
compress_dictionary[string(1,i)] = i;
}
string current_string;
unsigned int code;
unsigned int next_code = 256;
//Output file for compressed data
ofstream outputFile;
outputFile.open(filename + ".lzw");
for(char& c: input){
current_string = current_string + c;
if ( compress_dictionary.find(current_string) ==compress_dictionary.end() ){
if (next_code <= MAX_DEF)
compress_dictionary.insert(make_pair(current_string, next_code++));
current_string.erase(current_string.size()-1);
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
current_string = c;
}
}
if (current_string.size())
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
outputFile.close();
}
Using compiler settings (gcc version 5.2.0):
g++ -c -O2 -g -pg -std=c++14 lzw.cpp
10 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 10.txt
real 0m4.302s
user 0m3.072s
sys 0m0.632s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
45.83 0.55 0.55 compress(string, int, string)
36.67 0.99 0.44 14983735 29.37 29.37 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.50 1.08 0.09 10489603 8.58 8.58 show_usage()
5.83 1.15 0.07 4493878 15.58 44.94 operator[](string const&)
4.17 1.20 0.05 _Z22convert_char_to_stringB5cxx11PKci
0.00 1.20 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 1.20 0.00 3841 0.00 29.37 _ZNSt10_HashtableINSt7
0.00 1.20 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 1.20 0.00 1 0.00 0.00 ~_Hashtable()
20 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 20.txt
real 0m8.924s
user 0m6.504s
sys 0m2.008s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
49.33 1.47 1.47 compress(string, int, string)
34.56 2.50 1.03 29962271 34.38 34.38 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.05 2.71 0.21 8986654 23.37 57.74 operator[](string const&)
6.71 2.91 0.20 20975363 9.53 9.53 show_usage()
2.35 2.98 0.07 _Z22convert_char_to_stringB5cxx11PKci
0.00 2.98 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 2.98 0.00 3841 0.00 34.38 _ZNSt10_HashtableINSt7
0.00 2.98 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 2.98 0.00 1 0.00 0.00 ~_Hashtable()
30 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 30.txt
real 0m13.637s
user 0m9.665s
sys 0m2.984s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
45.59 1.86 1.86 compress(string, int, string)
37.25 3.38 1.52 44940806 33.82 33.82 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.60 3.69 0.31 13479429 23.00 56.82 operator[](string const&)
6.62 3.96 0.27 31461123 8.58 8.58 show_usage()
2.94 4.08 0.12 _Z22convert_char_to_stringB5cxx11PKci
0.00 4.08 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 4.08 0.00 3841 0.00 33.82 _ZNSt10_HashtableINSt7
0.00 4.08 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 4.08 0.00 1 0.00 0.00 ~_Hashtable()
----
== Team Members ==
# [mailto:ksanghun@myseneca.ca?subject=GPU610 Sanghun Kim]
# [mailto:hpark77@myseneca.ca?subject=GPU610 Heetai Park]
# [mailto:wlee64@myseneca.ca?subject=GPU610 Wonho Lee]
# [mailto:ksanghun@myseneca.ca?subject=GPU610,hpark77@myseneca.ca?subject=GPU610,wlee64@myseneca.ca?subject=GPU610 eMail All]
== Progress ==
=== Assignment 1 ===
==== Profiling: LZW algorithm ====
It's a simple version of LZW compression algorithm with 12 bit codes.
void compress(string input, int size, string filename) {
unordered_map<string, int> compress_dictionary(MAX_DEF);
//Dictionary initializing with ASCII
for ( int unsigned i = 0 ; i < 256 ; i++ ){
compress_dictionary[string(1,i)] = i;
}
string current_string;
unsigned int code;
unsigned int next_code = 256;
//Output file for compressed data
ofstream outputFile;
outputFile.open(filename + ".lzw");
for(char& c: input){
current_string = current_string + c;
if ( compress_dictionary.find(current_string) ==compress_dictionary.end() ){
if (next_code <= MAX_DEF)
compress_dictionary.insert(make_pair(current_string, next_code++));
current_string.erase(current_string.size()-1);
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
current_string = c;
}
}
if (current_string.size())
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
outputFile.close();
}
Using compiler settings (gcc version 5.2.0):
g++ -c -O2 -g -pg -std=c++14 lzw.cpp
10 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 10.txt
real 0m4.302s
user 0m3.072s
sys 0m0.632s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
45.83 0.55 0.55 compress(string, int, string)
36.67 0.99 0.44 14983735 29.37 29.37 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.50 1.08 0.09 10489603 8.58 8.58 show_usage()
5.83 1.15 0.07 4493878 15.58 44.94 operator[](string const&)
4.17 1.20 0.05 _Z22convert_char_to_stringB5cxx11PKci
0.00 1.20 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 1.20 0.00 3841 0.00 29.37 _ZNSt10_HashtableINSt7
0.00 1.20 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 1.20 0.00 1 0.00 0.00 ~_Hashtable()
20 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 20.txt
real 0m8.924s
user 0m6.504s
sys 0m2.008s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
49.33 1.47 1.47 compress(string, int, string)
34.56 2.50 1.03 29962271 34.38 34.38 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.05 2.71 0.21 8986654 23.37 57.74 operator[](string const&)
6.71 2.91 0.20 20975363 9.53 9.53 show_usage()
2.35 2.98 0.07 _Z22convert_char_to_stringB5cxx11PKci
0.00 2.98 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 2.98 0.00 3841 0.00 34.38 _ZNSt10_HashtableINSt7
0.00 2.98 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 2.98 0.00 1 0.00 0.00 ~_Hashtable()
30 MB text file
wlee64@matrix:~/gpu610/assignments/a1> time lzw -c 30.txt
real 0m13.637s
user 0m9.665s
sys 0m2.984s
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ns/call ns/call name
45.59 1.86 1.86 compress(string, int, string)
37.25 3.38 1.52 44940806 33.82 33.82 _M_find_before_node(unsigned int, string const&, unsigned int) const
7.60 3.69 0.31 13479429 23.00 56.82 operator[](string const&)
6.62 3.96 0.27 31461123 8.58 8.58 show_usage()
2.94 4.08 0.12 _Z22convert_char_to_stringB5cxx11PKci
0.00 4.08 0.00 4097 0.00 0.00 _M_insert_unique_node(unsigned int, unsigned int, std::__detail::_Hash_node<std::pair<string const, int>, true>*)
0.00 4.08 0.00 3841 0.00 33.82 _ZNSt10_HashtableINSt7
0.00 4.08 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z18convert_int_to_binB5cxx11i
0.00 4.08 0.00 1 0.00 0.00 ~_Hashtable()
----