By default, MinGW dynamically links to the C runtime that is available on most versions of Windows.
For the longest time however, it statically linked to libstdc++, and it is very likely that this is why you are seeing such an executable size difference.
Here is a snippet from the latest release notes however:
So make sure you have one of their V4 releases and try that. It should significantly decrease your executable size, at least for a simple hello world app. For example, here's a little test I did with a simple hello world app (my source code was in test.cpp):
NEW FEATURES SINCE MINGW GCC 3.4
-Shared libstdc++: Add -lstdc++_s to your link flags to link against a DLL
version of libstdc++.
That look about right to you?
CommandLine Executable Size
g++ test.cpp 844kb
g++ -Os -s test.cpp 437kb
g++ test.cpp -lstdc++_s 16kb
g++ -Os -s test.cpp -lstdc++_s 5kb
(Keep in mind the runtime dependency this creates though)