Blog
Page: 0 ... 5 ... 10 ... 15 ... 20 ... 25 ... 30 ... 35 ... 40 ... 45 ... 50 53
XP Has Left The Building
Date: 18/2/2006
My wintel box no longer boots XP. It gets past the "Starting XP" progress bar (in VGA on black) and then just before getting to the login screen all activity ceases with just a black screen. Nice.

Precipitating factor was that I had the machine spontaneously reboot while encoding with Auto Gordian Knot. I thought nothing of it, but when it tried to come back up, no dice. It boots in safe mode but I don't know what to frig with to fix the problem. I did boot once just after I turned off the firewire drive. But it's still off and booting fails.

Oh well, my trusty sidekick Mac mini will save the day. But I won't be getting any work done or read any email while the PC is dead. So don't expect anything much from me this week.

It's time to reinstall XP anyway. Thank you God that I have a hardware firewall :)
(0) Comments | Add Comment

Continuing Tales Of Optimization
Date: 9/2/2006
Once I had a working B+Tree I sought to intergrate this into Scribe to see how it worked with "real data". Well that was a dismal failure. You see being a disk based data structure rather than RAM based it sucked speed wise compared to the memory only system used by the v1.88 build of Scribe. So I looked at the code and there was a cache of sorts built in to keep B+Tree blocks in RAM for a while before flushing them to disk. I did a quick experiment to see how much the cached blocks were getting used and whoa, no caching was taking place. Well there yah go son, thats your problem.

So I started tinkering with the cache, first by fixing the bugs to get it working and then progressively changing it's parameters and implementation to improve speed. Initially by just fixing the bugs in the initial implementation I got a massive speed up. So instead of 50 keys/sec I got around 3600 keys/sec. Nice, but still slow compared to the old way. Then I realised that it wasn't a smart cache in that it cached the first n blocks and then that was it, so I implemented a system to remove older blocks when the cache was full. I bumped the cache size up to 256 blocks (from 128) and the speed went up to 3900 keys/sec. Ok, time to whip out the profiler and see where the time was being spent. Turns out that most of the time was going in linear searches through the cache which drastically limited the size of the cache and these get/put functions that converted data for serialization. So I reimplemented the get/put functions as macros, getting rid of the expensive function call and that made an immediate difference, speed was up to 4950 keys/sec.

The existing data structures were now holding cache size back, so I ripped out the array data structure and reimplemented with a binary tree for offset lookups and a doubly linked list for the least recently used que. That allowed the size of the cache to climb without hurting performance and speed increased again, with the cache size up to 1024 speed jumped up to 6400 keys/sec. The least recently used que was working a treat, with O(1) operation for all operations.

Size (blocks) Speed (keys/s)
1024 6386
2048 6960
3072 7238


But still I wasn't convinced. From cs101 any programmer knows that binary trees have O(logn) complexity for insertion, deletion and search. Now I know of another data structure with essentially O(1) complexity for all those operations. A hash table.

So in goes the hash table and then I ran the tests again. 1500 keys/sec. Huh? Ok, 2 things could be happening here, a) I could have chosen a sucky hashing algorithm and b) my code is probably buggy. To fix the bugs I wrote a data structure verify function that scanned the entire thing and check for conformance to the rules. This ran everytime I changed something in the structure, and it saved heaps of time. Then with the bugs out of the way I got down to checking the quality of the hash algorithm. I tested the number of hash table collisions for each hashing algorithm and eventually settled on a shift and a modulous.

Size (blocks) Speed (keys/s)
4096 7683


Now I felt I was wringing out the last of the performance from the data structure. Still when I plugged it into Scribe I was getting about 100-130 messages / sec when rebuilding the spam word database. This is compared to the 600 messages / sec with a straight memory only hash table. So it took about 5 times longer to build the word DB.

So currently I've given up with using the B+Tree directly during word DB rebuilds and I've gone back to the memory sucking hash tables. Then instead of writing the hash table to disk I dump it all to the B+Tree instead so that I can access the data without loading the entire thing into memory. This keeps the footprint of Scribe nice and low for normal day to day running, and there isn't that expensive word DB load that kills performance during the first mail receive of the session.

The only problem now is that during the word DB rebuild my debug build sucked down a cool 1gb of RAM, seriously paging out to disk (I've got 512mb installed). This is obviously unacceptable so I'll have to look at that before a release happens. But I'll probably remove the "rebuild word DB" function entirely and rely on incremental edits and mail is received and moved between folders. I'm still toying with the idea of adding mail bit by bit to the word DB's as the user moves around the folders, thus acheiving the indexing incrementally and thus the speed of the B+Tree's is not so much of a problem. Also the actual word counts are not accurate yet, there is an issue in the mail -> word list function that I've been working on for a couple of days now. Damn charsets and dodgy email clients make things so complicated.

Anyway, enough said, I'm still working hard on the software and a release will happen in the next few weeks.
(2) Comments | Add Comment

Optimization
Date: 3/2/2006
Recently I've ported some B+Tree code to windows to use in Scribe for storing the spam database word indexes. The current system takes a lot of time to load into memory and uses too much memory. I spent some time optimizing the existing code, but fundamentally it's design is flawed. Really the data needs to stay on disk and be arranged for random access (by key) without loading much of the file into memory. These is an existing data structure for that called the B+Tree. It's now finding it's way into commonly file systems (like ReiserFS), and was the basis of the BeOS File System.

However my point is that Scribe is probably going to use B+Trees for it's spam word DB. To test the code I've been reading in my current spamwords.wdb file and exporting it to the new B+Tree format. The .wdb file is fairly optimal in it's size, mines 762kb, so thats our baseline. The B+Tree files are less optimal in storing raw data, because of the overhead of their structure, but they have other very desirable qualities.

Once I got the B+Tree code actually working, I began finding the best parameters for the B+Tree, my initial attempt created a 4+mb file, eek! B+Trees are parameterised by block size and order. The order (n) is an indicator of the desired number of keys per block. The B+Tree tries to keep the number of keys between n and 2*n. The block size and order are inter-related, if the order is too small for the block size the blocks have lots of wasted space, if the order is too large, the blocks get full and have to be split up into multiple blocks too soon. So I worked where the sweet spot was for my typical data (using 256 byte blocks):

Order Size
14 2088kb
16 1813kb
17 1706kb
18 1692kb
19 1589kb
20 1614kb
24 1721kb
28 1945kb


However on top of that, the order effects the speed of the data structure, because the larger the order, the more keys in the block and thus more linear searching of keys at the leaf level.

I found the sweet spot for 512 byte blocks was quiet a bit slower than the sweet spot for 256 byte blocks for this reason.

I'll be putting this into the bayesian implementation in Scribe v1.89 test1... it bring down the memory footprint and speed up the first mail receive a fair bit... esp if you have large word databases.
(1) Comment | Add Comment

XP Screen Madness
Date: 31/1/2006
I've found that when you hook an XP machine up to a KVM and boot it while the KVM is displaying the other machine, XP sees there is no monitor attached and ignores the refresh rate set in the display settings. In my case I want 1280x1024@32bpp and 75hz refresh. Which is fine if I boot the machine with the KVM switched to the XP box, otherwise the machine boots into 1280x1024@32bpp and 85hz refresh. When I do switch the KVM to the XP box the LCD says "Input Out Of Range". Now I wrote a command line program to tell me the current screen mode, ssh'd in from the Mac mini while XP was in this "Out Of Range" mode and ran the cmd line app. Thus I actually know what the out of range mode is.

The next step of course is to stop XP from setting the refresh to 85hz. Now I've googled around and some people seem to think that there might be an Nvidia registry setting that forces the refresh rate but so far no luck in getting that to work.

I added some functionality to my cmd line app to set the video mode (inc refresh) as well, and then called it from a remote ssh shell, but it complains about not being able to set the video mode. Which is not surprising I guess. (It does work fine from the local console.)

Now I'm thinking that maybe a Windows service needs to be installed that sits there polling the video mode and then if it sees an out of range mode it tries to reset the screen to some default. I havn't written a service before and I have my doubts as to whether a service can change the screen resolution/refresh. But it's worth a try.

The reason I would have to run it as a service is that when the machine boots, it goes to the select account screen that has no user actually logged in. At this point I only have services running, thus the need to run as a service. Otherwise I have to log in blind. Which is actually what I do to fix the problem at the moment. Log in as one user and then log in as another user, all blind, using the keyboard only. XP resets the screen mode when logging in to the 2nd account and the LCD shows the desktop.

I'm not even sure if it's the video card, XP or the KVM at fault but it's really really annoying.

*sigh*

Update: Last night I installed the resolution check cmd line app in the "All Users" startup folder such that it checks the resolution and refresh and changes it to something acceptable while logging in to each account. This way all I have to do is hit enter when the machine has finished booting and it'll switch to a valid screen mode. So while it's not "ideal" it's now a fairly benign problem.

I've packaged the res/refresh change program (with source) and made it available here.
(0) Comments | Add Comment

Quiet PC
Date: 29/1/2006
After years of tinkering with making my PC quiet I think I'm finally on the verge of actually acheiving an almost silent PC. Recently I installed a Zalman fanless northbridge chipset heatsink because the little 40mm chipset fan was making disturbing noises like the bearings were failing and the PC was still far too noisy. And over the last few days I've been getting a number of load related system freezes. So I thought I'll pull the cover off and trouble shoot.

Over the years I've been picking up super quiet fans like the Pabst 8412NGL (12db) which I'm using on the CPU and the SilenX 120mm (14db) on the case. And I never really saw the point and the system wasn't much quieter. So finally I figured that I could test the system components in isolation to see how noisy each was. So I pulled all the fans (bar the CPU) and HD power cables and powered up. Silence. System booted... wow! Ok... so I worked my way around the system pluging each device back in one at a time and lo and behold one of the hard disks was making 90% of the noise. So it's out and the system is finally almost silent. The fans I bought are actually very good.

My remaining issue is that under load the Pabst fan doesn't push enough air to cool the CPU and it overheats and hangs. So I'm schemeing up plans to beef up the CPU fan with either a temperature sensitive unit or maybe some ducting to adapt one of the 120mm SilenX fans to the 70mm copper heat sink. The SilenX fan pushs twice the air the Pabst fan does.

If only I'd been lateral minded enough to use my code optimisation skillz sooner *sigh*
(0) Comments | Add Comment

Mpeg2 Non-Destructive Editing Workflow
Date: 27/1/2006
I am in the process of editing out duplicate scenes in 6+ hours of DVD format MPEG2 files. Joy!

And at the moment the workflow consists of:
  • Load file in to Media Player Classic and write down rough start/end points of each duplicate scene.
  • Load PVAStrumento to demux the MPEG2 stream into separate video and audio.
  • Load these files into Cuttermaran and mark all the in/out points in the file. Generally the "in" point marks the beginning of a part you want to keep and the "out" point marks the end. You should not make the out point the first I frame of the next scene but rather the last B or P frame of the previous scene, otherwise you get a 1 frame flicker of that scene at the out point.
  • Then as I'm saving the edited video in Cuttermaran I ask it to remux the streams together.


This seams to provide excellent results but it is somewhat time consuming. Is there a better way to delete scenes in MPEG2 without re-encoding any video? (No shareware or warez please)
(5) Comments | Add Comment