speed tips -- large (21k songs) Match library on iPhone 4

Ever since enabling iTunes Match on my iPhone 4, I've been seeing lots of performance issues. Not only when actively using the Music app -- the entire phone is slow, and unrelated apps like Facebook now regularly crash. The only way to get Music to work properly is to double-click Home and manually kill every other app.

It's been getting worse over time, and I suspect that the size of my library is the cause (was appx 19k songs when first enabling Match, now pushing 21k songs).

Any suggestions on improving it? I'm still on iOS 5.1.1. I would update to 6.1 if I expected performance improvements, but I'm worried it will just get worse. In the past, Apple's iOS upgrades haven't been friendly to older phone models.