Crunching bytes
25/Jun 2009
As you’re probably aware - there ain’t such thing as ‘too much memory’. It doesn’t matter how much there is, it’s never enough. Even if we fit, it still pays off to use the smallest structures possible, as they’re more cache friendly. The more we can squeeze them (without wasting too much time for depacking of course) - the better. Recently, I’ve been optimizing some X360 code and one of main problems (as usually with consoles) were related to cache-usage. There were some often used structures, that could probably be at least laid out more efficiently. At first, I’d examine them manually, but it quickly became too mundane. I thought of writing a simple tool that’d dump basic info about used types for me.
I already had experience with using DIA SDK (MemTracer and some of my other projects, that I hope to finish one day, including reflection system), so it seemed easy enough - I could extract all the information I needed from PDB (MSVC only, but that’s fine for my situation). After few hours I had my initial C++ commandline application. It worked nice, I could either display layout of specified type or make it list top X most ‘wasteful’ structures. However, as soon as I finished, I thought it would be more comfortable to use if I could analyze all the structures, sort them by size/padding, see their details (’ that should teach me to think about usage cases before actually starting to code, but I’m not sure if I’m not beyond salvation already). It’s rather trivial to use DIA from C# (actually, in many aspects it’s way cleaner than C++ version), so version 0.2 was actually even easier to code. Meet Cruncher# (stupid name, I know, but Sizer and Crinkler were already taken). It’s very simple, but works very well for my (limited) purposes. Source code is available, so feel free to hack until it works for you. Known bugs/limitations:
it gets a little confused when encountering unions/bitfields,
it only cares about UDTs (User Defined Types).
there’s no information about vtable, base classes, etc.
I also briefly considered coding analyzer that would generate optimal class layout to minimize padding. In the end, didn’t decide to bother. Without knowing access patterns in many cases it could do more harm than good (splitting variables that are always accessed together for example). Besides, the problem itself wouldn’t be trivial, so not the best bang-for-the-buck ratio.
Final source code and executable can be downloaded here.
After starting the application, simply load PDB file (Ctrl+O). It’ll display all the UDTs in left panel and details of selected type in the right one, should be pretty self-explanatory, sample screenshot above (it’s from version 0.1b, later I added possibility of filtering symbols, it follows standard C# filter syntax, so for example to see everything related to namespace rde, type ‘rde::’).
PS. Freakin’ Norwegian is going to cancel Warsaw-Stockholm connection in August :/. Was fun while it lasted (700SEK for both way ticket? Yes, please).
[Edit] Uploaded new, fixed version, thanks to hcpizzi for reporting a bug (see comments for details).
Old comments
Arseny Kapoulkine 2009-09-15 18:37:14
Remembered about this once again through Twitter link :) Got a msdia90.dll, registered it - now it works! I wonder if there’s an official way to do it (except installing MSVS 2008…).
admin 2009-09-08 21:27:18
Yes, that’s DIA. If I remember correctly I used msdia90.dll from latest Microsoft’s Debugging SDK. C# tends to act weirdly sometimes…
Arseny Kapoulkine 2009-09-08 05:20:33
I can’t get it to work for some reason. Once I load a PDB file, it throws an exception:
System.Runtime.InteropServices.COMException (0x80040154): Failure while getting COM class object factory for component with CLSID {4C41678E-887B-4365-A09E-925D28DB33C2} because of the following error: 80040154.
?? CruncherSharp.CruncherSharp.loadPDBToolStripMenuItem_Click(Object sender, EventArgs e) ?? c:!projects\rde\tools\CruncherSharp\CruncherSharp.cs:?????????° 35
?? System.Windows.Forms.ToolStripItem.RaiseEvent(Object key, EventArgs e)
?? System.Windows.Forms.ToolStripMenuItem.OnClick(EventArgs e)
?? System.Windows.Forms.ToolStripItem.HandleClick(EventArgs e)
?? System.Windows.Forms.ToolStripItem.HandleMouseUp(MouseEventArgs e)
?? System.Windows.Forms.ToolStripItem.FireEventInteractive(EventArgs e, ToolStripItemEventType met)
?? System.Windows.Forms.ToolStripItem.FireEvent(EventArgs e, ToolStripItemEventType met)
?? System.Windows.Forms.ToolStrip.OnMouseUp(MouseEventArgs mea)
?? System.Windows.Forms.ToolStripDropDown.OnMouseUp(MouseEventArgs mea)
?? System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks)
?? System.Windows.Forms.Control.WndProc(Message& m)
?? System.Windows.Forms.ScrollableControl.WndProc(Message& m)
?? System.Windows.Forms.ToolStrip.WndProc(Message& m)
?? System.Windows.Forms.ToolStripDropDown.WndProc(Message& m)
?? System.Windows.Forms.Control.ControlNativeWindow.OnMessage(Message& m)
?? System.Windows.Forms.Control.ControlNativeWindow.WndProc(Message& m)
?? System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)
(error message was in Russian originally).
I’ve looked up the error and it’s REGDB_E_CLASSNOTREG (Class not registered).
My PDB files are from MSVC2005, can it be a problem? Also maybe I need some external dependencies, like, new DIA runtime or something?
Arseny Kapoulkine 2009-09-08 05:27:51
Installing VC2008 redist did not help; downloading and registering (via regsvr32) msdia80.dll did not help either.
Aras Pranckevicius 2009-06-27 11:20:55
Nice! SuperBar and SuperFoo (screenshot) for the win :)
hcpizzi 2009-06-30 15:52:13
Hi! I just tried it. This can be very useful! really nice tool indeed.
I just discovered a little bug, though. If a class inherits from a zero sized base, you get an incorrect padding measure. A sample:
class Base
{
};
class Derived : public Base
{
char mFirstMember[1024];
char secondMember;
};
And the output (slightly reformatted):
Symbol: Derived
Size: 1025
Total padding: 1023Members
mFirstMember 0 1024
Base: Base 0 1
****Padding 1 1023
secondMember 1024 1
Seems like it gets confused by the base having the same offset as the first member. Just changing CompareOffsets to sort by size if the offsets are equal seems to solve the problem.
private static int CompareOffsets(SymbolInfo x, SymbolInfo y)
{
return (x.m_offset == y.m_offset) ? ((x.m_size == y.m_size) ? 0 : (x.m_size < y.m_size) ? -1 : 1) :
(x.m_offset < y.m_offset) ? -1 : 1;
}
Hope this helps!
admin 2009-06-30 21:47:28
Yes, that’s my laziness biting me in the ass again. The problem is that I sort all the members by offset. It’s only needed for base classes, because member variables are in the correct order in PDB already. I thought it could be a problem when mixing both (bases/members), but my quick tests didn’t confirm it. Anyway, I fixed it and uploaded a new version, thanks for reporting (it now makes sure base classes go before member variables).
Structure Padding Analysis Tools | Rachels Lab Notes 2009-10-22 15:19:07
[…] yet, occasionally, something slips through. So it’s nice that somebody wrote a tool – Cruncher# – to just load your PDB and examine all your structures for unnecessary […]
admin 2010-03-29 20:21:34
@Jumpster: that’s exactly right (= layout conclusions). With classes is exactly the same (the only difference in C++ is that class members are private by default, generated code is identical).
About the optimal structure suggestion – it’s probably a good idea, but problem is not trivial (variation of knapsack, basically), so it’s something I postponed until I have more free time.
Jumpster 2010-03-19 23:55:04
It took me a bit to envision what you are saying, but I get it now: Using your example;
struct one {
byte byte_1; // 3-bytes padding
int int_1;
byte byte_2;
byte byte_3;
byte byte_4; // 1-byte padding
}; // sizeof() = 12
struct two {
byte byte_1;
byte byte_2;
byte byte_3;
byte byte_4;
int int_1; // No padding
}; // sizeof() = 8 -> 33% savings…
I’m glad I stumbled upon your site. In all my years of programming, I never realized the inefficiencies caused by my data structures.
Just a question tho, although I could check this myself - but if you already know the answer… :)
Anyway, since classes and structs are essentially the same, then is it safe to assume class structures have the same types of inefficiencies?
I tend to place class definitions (methods/member vars/etc) in what I feel is a logical point, I assume that classes should be looked at too?
Anyway, thanks for the info. That was something I didn’t know.
Regards,
Jumpster
Jumpster 2010-03-20 00:11:12
Perhaps a future revision to Cruncher# may offer a suggestion of a new structure format that minimizes the padding requirements?
Just a suggestion, pretty cool program!
Me likey,
Jumpster
admin 2010-03-17 08:58:37
You understand it correctly. That’s why I don’t advocate using #pragma pack(1) (this would force 1-byte alignment and eliminate padding, the ‘easy’ way). Instead we want to minimize ‘holes’ caused by inefficient alignment. For example, if there’s a byte, followed by int, followed by 3 bytes, it’d be more effective to rearrange it so that 4 1-byte member go first, then goes integer. In real world cases it’s usually impossible to eliminate them completely, but I’ve been able to reduce size of important structures by ~10-15% just by shuffling variables around.
Jumpster 2010-03-17 02:30:33
I realize I’m a bit late here, but I’m a bit confused…
I understand the reason for saving memory (ie: reduce memory padding to save resources) but I was under the impression that aligning structures to a native size (4-bytes on 32-bit systems / 8-bytes on 64-bit systems) improves efficiency due to the memory/cache access improvements? Am I misunderstanding something here?
Regards,
Jumpster
Friday links 56 « A Programmer with Microsoft tools 2014-02-21 03:25:12
[…] Crunching bytes | .mischief.mayhem.soap. […]