Showing posts with label Computer Science. Show all posts
Showing posts with label Computer Science. Show all posts

17 August, 2010

[C++ template] Is template better?

I wrote a lot of template code recently and using some amazing trick to solve my problems. However, when I was studying those template tricks, I feel like that they invented template programming because C++ is not perfect. But... On the contrary, sometime I think that C++ is perfect because of its powerful template features.

The most attractive part of template programming to me is its run-time performance. It generates the code in compile-time and eliminate a lot of branches at run-time. If you compare the template programming with C++ polymorphism, those approaches are different from the beginning. The first one ultimately leverage the power of compiler but the second one is depends on its run-time behavior.

So what kinds of benefits can template programming provides in compile-time? To explain in detail, we need a real example to demonstrate it.
Problem:
  1. Write a connection class with two types: client and server. The connection class have one method: "sayhi()", the server has to print out "server: hi" and client has to print out "client: hi".
  2. Write a function, which parameter is a pointer to the connection class and its job it to invoke the "sayhi()" method 10 times in a for-loop.
The next is the straightforward answer without using template trick.

After rewriting the code using template programming skills, the code will be like:

Let's see what can the compiler do for us, I used optimization level 3 to compile the source code, and I will post part of the assembly code and do the comparison below:
ASM of the original source code:

At line #18, you can see here is a branch corresponding to the line #9 in the original source code. So we have a branch condition in a for loop, the compiler cannot optimize it.
ASM of the template source code:

You can see that there is no branch in the template version because compiler can optimize it. Moreover, the for-loop has been unrolled! The compiler cannot unroll the first version because it is not able to know if it is a server connection or client connection in the for loop.

By using this example, we can see how template programming reduce the run-time overhead and its ability to "be optimized" by compiler.

13 August, 2010

[C++ template] Use one member function to return different class member with different type.

Why would I need a class member function to return different type of member variables?

Sometime you will need a class that its behavior will be a tiny little different base on its role. e.g. server and client. When implementing server/client classes, they both need a send function and a receive function and the implementation of send/recv function on server class are almost the same as in the client class, the only difference in their implementation might be the class member they manipulate.
To simplify the problem, here is a concrete example:
We want to implement an adder class that can add two values and return the result. There will be two types of adders: int_adder and string_adder, and they have to use the same code base because they are using almost identical logic.
So the base class will be look like:
class base_adder
{
    public:
        //T is either inner_int_type or inner_string_type
        T getDataBlock()
        {
        
        }

        void exec()
        {
            //add b to a
        }

        //T is either int or string
        T getResult()
        {

        }

        struct inner_int_type
        {
            inner_int_type():a(0), b(0), result(0){}
            int a, b;
            int result;
        };

        struct inner_string_type
        {
            string a, b;
            string result;
        };

        inner_int_type int_data_block;
        inner_string_type string_data_block;
};

OK, here is the base adder, but remember that we have two types of adder, int_adder and string_adder. How do we distinguish it? The straightforward idea is using constructor and pass the type into it. Then the constructor of the base_adder would be like:

class base_adder
{
        enum
        {
            int_adder,
            string_adder
        };

        base_adder( int type ):m_adder_type(type){}
        ...
};
So far so good, however, let look at the exec() member function first, how do we know which data block to use? Should we use the int_data_block or string_data_block? It is OK to use if...else statement to do this:

This implementation is not efficient because of the extra if...else statement. However, it is not the worst part, let look into the getDataBlock member function. Different types of adder has to return different types of data block (inner_int_type or inner_string_type). We cannot even use if...else statement to do that! Because one member function can only return one type of result. Therefore, the following code is illegal:

When using template type as the return type of a function, you have to specified the return type while using that function: e.g. getDataBlock<inner_int_type>(). I will explain why I hate this later.

You might think of "function overloading"! Yes, we just need to overload getDataBlock function to return different types of data, like this:

You can see that the code are duplicated, and you also need to overload getResult function. If we add more functions like getA(), getB() ... etc. We have to overload them all.
I am looking for the perfect solution to minimize the code duplication. Hence, why not using template to do that? The actual problem I am facing is "I need to know the return type base on the type of adder". To solve this problem, type trait is handy here, and we can also use some trick to deal with exec() and getDataBlock() function:

Everything is working now, following is the using example, you can see that we don't need to take care the return type, we just use it directly without thinking:

Here is the program output:


Even though everything is working now, but you can see that I still use function overloading to return different types of data block, the source codes are still duplicated! I need a way to return different blocks base on the type of adder! The solution is using a new template trick "type2data", the trick works as follow:

The code is neater, no duplication anymore! The "type2data" trick does help.
Nevertheless, it is still not perfect. Consider adding a new method "getResult", the return type of this function is the type of "result" in the data block. We need to write new pair of type2data for this purpose, like this:

Why not using template to implement "type2data" function? OK, the code would be like:

It is a disaster to have a template return type, because you have to use this template function like this:

It ruined my original purpose -> "I don't want to care about the type while using this class". The only solution is to have a universal generic type2data function. It is our final goal. After analyzing the "type2data" function, I found out that defining the return type (RET) as one of the template parameters is unneeded, because the return type must be one of the input type (TYPE_A or TYPE_B). So my final generic type2data is implemented as follow:


The code is simple and short and easy to understand now. Using C++ template, we reduce some runtime overhead like the if...else statement and make the code more flexible and more reusable.
Anyways, if you want to show off your template skills, you can implement the type2data likes below, and it is actually my first version of type2data:

I hope this article is useful to you :)

27 April, 2009

Using C++ Template to Create Debug Message

We usually use some macro to create debug message, likes: #define DEBUG_LOG(str) ....

I found out that we can use c++ template to achieve to same functionality. See the following code:

template<int T>
class Debug_Msg
{
public:
wstring str;
Debug_Msg( wstring s ):str(s){};
};

template<int T>
wostream& operator<<(wostream& wos, Debug_Msg<T> d);

template<>
wostream& operator<<(wostream& wos, Debug_Msg<0> d)
{
return wos;
}

template<>
wostream& operator<<(wostream& wos, Debug_Msg<1> d)
{
wos << d.str;
return wos;
}

To print out the debug message: 
wcout << Debug_Msg<1>("This is the debug message");

C++ template provides more flexible way to handle debug message.

12 January, 2009

Book: Effective STL

Recently I read a good book about STL, "Effective STL". I made a simple summary about this book.
The following list are the items which I think are important and I did not know most of them at first.

Item 4. Call empty instead of checking size() against zero
You should prefer the construct using empty, and the reason is simple: empty is a constant-time operation for all standard containers, but for some list implementations,
size takes linear time.

Item 5. Prefer range member functions to their single-element counterparts.
It is definitely faster, but be careful with the pointer.

Item 6. Be alert for C++'s most vexing parse.

Item 7. When using containers of newed pointers, remember to delete the pointers before the container is destroyed.
One thing you must never be fooled into thinking is that you can arrange for pointers to be deleted automatically by creating containers of auto_ptrs.

Item 8. Never create containers of auto_ptrs.

Item 9. Choose carefully among erasing options.
use earse: vector, dqueue, associative container
use remove: list

Item 17. Use "the swap trick" to trim excess capacity.
vector(contestants).swap(contestants);

C++ guarantees that local objects are destroyed if an exception is thrown

Item 23. Consider replacing associative containers with sorted vectors.

"maps and multimaps keep their elements in sorted order, but they look only at the key
part of the element (the first component of the pair) for sorting purposes, and you must
do the same when sorting a vector. You'll need to write a custom comparison function
for your pairs, because pair's operator< looks at both components of the pair."

"Interestingly, you'll need a second comparison function for performing lookups. The
comparison function you'll use for sorting will take two pair objects, but lookups are
performed given only a key value. The comparison function for lookups, then, must
take an object of the key type (the value being searched for) and a pair (one of the
pairs stored in the vector) — two different types. As an additional twist, you can't
know whether the key value or the pair will be passed as the first argument, so you
really need two comparison functions for lookups: one where the key value is passed
first and one where the pair is passed first."

Item 29. Consider istreambuf_iterators for character-by-character input.

Item 30. Make sure destination ranges are big enough.
Use inserter: front_inserter,inserter,back_inserter

v.erase(remove(v.begin(), v.end(), 99), v.end());

Item 41. Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref.

Cite form the Wikipeida:
Deques are often implemented using a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Two common implementations include:

* Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
* Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.

09 January, 2009

WinXP: How to use DHCP and have static IP on the same NIC

To setup a virtual NIC under Linux is easy:
ipconfig eth0:0 netmask broadcast
Finished!

However it is not easy to do that under WinXP when you want to use DHCP but also need a static IP on the same NIC. According to this website http://www.petri.co.il/configure_tcp_ip_to_use_dhcp_and_a_static_ip_address_at_the_same_time.htm

Using regedit to go to "HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters\Interfaces\" and find your NIC. Then add the ip and submask to the regkey.

Disable your NIC and the enable it. After that, you can use ipconfig /all to check if it was work.

06 January, 2009

"Submit" is preserved word in JavaScript

Do not named your function "submit", you can not even overload it!

04 December, 2008

SSH Tunnel Through Multiple Servers

For example, you want to use sftp connect to server C. Because of the security reason, you can not access server C directly from your local machine. Finally you figure a route, the only way to access to server C is local->A->B->C.
How do we set up ssh tunnel through these servers(using OpenSSH)?
1. on your local machine
ssh -f -N -L2000:localhost:2000 user@A
2. on server A
ssh -f -N -L2000:localhost:2000 user@B
3. on server B
ssh -f -N -L2000:localhost:22 user@C
Done! Now you can connect to localhost:2000 to access server C.

P.S. Pexpect is a nice python module to interact with apps through ssh.

27 September, 2007

Charm++: Using ROV in module

Charm++ compiler will compile the .ci file into two files, .decl.h and .def.h.

But there is a little bug in this scenario, the compiler put the "extern rov" in the .def.h file.
What is wrong with that? Because when we write a module for other application, other users will only include the .decl.h file but not the .def.h file. So the extern statement should be in the .decl.h file. However, you can extern the rov in your .h file, then other users who want to use your module have to include that file too.

30 August, 2007

Compiz Fusion: Finally!

Finally they enable screen edge to trigger "show desktop"~
I have waited for this patch for a month...

Viva Compiz Fusion~~

24 August, 2007

C++ Template Class Static Member Declartion

template
class list
{
public:
class node
{
private:
public:

T data;
node *next;
};
private:
static node *pool;
};

How to declare static member "pool"?
template list::node *list::pool; --> incorrect!
template (typename | class ) list::node *list::pool; --> correct!

it is a little weird and very unfriendly... If I use "class" keyword to declare, I would be confuse by myself...

23 August, 2007

Perfect Mail Server == Google App + EveryDNS

I am really tired of setting my postfix server to handle many weird problems, for example, I can not get the mail from yahoo, gmail, pchome... I already set up my MX record, PTR record A record...
But it just doesn't work!!!
Google App is every useful in this situation, you can sent/receive mail via gmail server and still using your domain name!!
EveryDNS is a free DNS, it support MX, CNAME, A, NS record, and it is accepted by google!

Some notes:
在hinet的DNS組態設定
DNS Server Name IP
一 ns1.everydns.net 38.99.14.207
二 ns2.everydns.net 216.218.240.206
三 ns3.everydns.net 80.84.249.169
四 ns4.everydns.net 63.219.183.200

EveryDNS的組態設定
ooxx.com.tw A 59.120.241.123
ooxx.com.tw MX ASPMX.L.GOOGLE.COM 1 3600
ooxx.com.tw MX ALT1.ASPMX.L.GOOGLE.COM 5 3600
ooxx.com.tw MX ALT2.ASPMX.L.GOOGLE.COM 5 3600
ooxx.com.tw MX ASPMX2.GOOGLEMAIL.COM 10 3600
ooxx.com.tw MX ASPMX3.GOOGLEMAIL.COM 10 3600
ooxx.com.tw MX ASPMX4.GOOGLEMAIL.COM 10 3600
ooxx.com.tw MX ASPMX5.GOOGLEMAIL.COM 10 3600

Some Tips for Postfix

1. make sure that the name in /etc/hostname is the same as your real domain name
2. in main.cf, in $mydestination, put localhost before any other domain name
3. remember to set up MX and PTR record, you can do it via your DNS service provider

19 April, 2007

Charm++: Design Your Parallel Program

You can to divide your program into many stage, and you have to make sure your will run stage by stage. Otherwise, you will encounter very weird problem.

It is possible to your program that it jump stage to stage, so be careful of the ordering.

18 April, 2007

Charm++: User-Defined type

How to use user-defined type in charm++?

In ooxx.C, put the class/struct declaration before "#include "ooxx.decl.h"", and insert "#include "charm++.h" " at the first line.

For example:
#include "charm++"
class myclass
{
public:
void sayhi(){}
void pup(PUP::er &p){}
};
#include "haha.decl.h"
your code...

Remember to implement the PUP method for your classes.

12 March, 2007

A Terrible Week

Distribute System作業遲交.... 10%還不知道能不能補交,真是糟糕阿
明明就是不難的作業,只能說socket programming的變數實在是太多了,不過這次在兩天內寫了2500行也倒是一個新紀錄XD

昨天晚上被一個BUG困擾超級久,差點要去撞牆了,後來找到那個不可思議的BUG

gcc -O3 flag

這實在是太慘了,手賤下了Opmization Level 3,然後就死在那邊,其實原因是助教提供的檔案,有一個global variable會被upcall function用到,但是他沒有加上volatile關鍵字!!!

這門課的助教實在是很...,就是因為這樣我才擔心不能遲交...

11 March, 2007

Makes "errno" Thread-Safe

Just define _REENTRANT before include pthread.h

#define _REENTRANT
#include

Is it really correct?...

08 March, 2007

Unfamiliar with C...

沒想到Distributed Systems的作業居然給我規定用C來寫....
我之前寫的library一點屁用都沒有了!!

然後我實在是太久沒有寫純C的程式了... 犯了一大堆記憶體上的錯誤,我要去撞牆了ORZ

26 December, 2006

Design Pattern Final Presentation

昨天一個晚上沒睡就在弄今天早上的報告,弄到9點快十點鐘於弄好了,不過....

今天才剛開出程式就出現問題了orz,gui的完整度太低,沒有加上應有的功能,我承認我完全忘記了,全部在弄html的產生,還想辦法多搞一些pattern上去,方向錯誤阿。

在頭影片第一頁Composite Pattern大概就停了一節課吧...由於我懶的加上新的node,造成了整個結構鬆散,可以說是自作孽,其實我早就有預感那邊會出現問題,只是加上去會很花時間,因為我有些地方把結構寫死了,要在寫程式之前弄一個全面性的架構實在不可能,可是慢慢建立起來又會有設計不當的問題,看來我寫程式的功力完全的不夠阿orz。接下來每一頁的頭影片都是按的心驚膽顫,不過我也更新了很多的概念,也有新的想法,雖然一直被說有錯誤,不過感覺其實還不錯啦。
這門課真的是讓我學到很多東西,Design Pattern為何物,我現在總算有個頭緒了,但是要正確且適當的套用Pattern我還差的遠阿... 這真的是一門超級困難的學問,有時候在設計的時候想太多也不對想太少也不對,這應該是要靠經驗吧orz,"用良好的pattern會讓程式碼越寫越短",我剛剛好反過來,我要學的東西實在是太多了... 希望以後能當程式架構設計師而不是只是單純的寫程式而已...
這門課到今天可以說是告一個段落啦~ 收穫很多,值得一修,這大概是我上大學覺得第二門值得修的課吧XD

19 December, 2006

Singleton Pattern

The meaning and benefit of using singleton pattern is:
  • make sure there is only one instance
  • only have to write three static method(in simplest case)
If you do not want these feature, you can just use a global variable.

01 November, 2006

Design Pattern: Book-MVC Project

Change Log:
  1. Downgrade to JAVA 1.4
  2. Add new button "Save Page as HTML", you can save the page to html now.
  3. Add new package "app", put class "BookDisplayer" inside.
  4. Add new package "layout", use Strategy pattern inside.
    • There are two layout generator:
      • PlainTextLayoutGenerator
      • HTMLLayoutGenerator
  5. Add new package "factory"
    • class "FormatterFactory" can provide different formatter to component, use Singleton Pattern.
  6. Add new class "BookHTMLPrinter" into control package, which can create a html file.
Implementation:
  1. layout package
    • Interface "Composition"
      • method "dolayout" will use the current layout generator to generate the component's layout.
    • Interface "Page"
      • defined the basic method for page
        • setPageWidth( int w )
        • setPageHeight( int w )
        • getPageWidth()
        • getPageHeight()
        • getPageId()
        • insertline(String line)
        • getContent()
    • Interface "LayoutGenerator"
      • method "compose" will use the formatter to construct the pages, and return a list the page.
    • Class "BookComposition"
      • implemented interface "Composition".
      • have a list of compoenets.
      • have a LayoutGenerator's reference which point to the current layout. generator.
    • Class "HTMLPage"
      • implemented interface "Page".
      • generate page in html formate.
    • Class "PlainTextPage"
      • implemented interface "Page".
      • generate page in plain text foramt.
    • Class "PlainTextLayoutGenerator"
      • implemented interface "LayoutGenerator".
      • generate pages with fixed line width, and page height.
    • Class "HTMLLayoutGenerator"
      • implemented interface "LayoutGenerator"
      • generate pages with html tag.