Time for a battery change?

Yesterday I noticed a slight bulge at the bottom of my 39 month old 13" Mac Book White. Coconut battery tells me I got 4216/5450 capacity, battery load cycles 581.
Besides the bulge, I do not see any other problems, visually as well as in performance.
Is it time for a battery change?

Yup, if the battery bulges, it's gone bad. This has only happened to me once.

Thanks Bear. Now to hunt for an iStore near me.
Is there anything like extended battery for Macs? If I remember Dell offers one. Normal battery lasts x hours, where as extended lasts x+ hours.

Call me cynical, but why aren't all Dell batteries "extended". Sounds like a racket to me... "Oh, you wanted one that works? That's extra!"

P.S. My battery was out of warranty by the time it boofed up, but I recall that they took off a lot on the replacement so it didn't cost a whole lot. I'm lucky to have two Apple stores in town.

I got a free replacement when my battery did that under warranty.

You battery is less than 80% capacity; at that point it is worth getting a replacement, even if it doesn’t bulge. Though I am still using a Dell battery down to 59% capacity.