Don't change the Wordpress permalink structure!

I changed the permalink structure of my video games site the Games Master and I noticed the traffic I'm receiving now dropped dramatically.

A bulk of my traffic comes from search engines. When I changed the permalink structure, the pages indexed by search engines returned a 404 error because the URL had changed. My URL structure before was

/%postname%-%monthnum%%post_id%

Now, I've read that (and I'm pretty sure I knew this before but I didn't really care) this type of permalink structure can be very taxing on the web host and can cause major slowdowns in blogs with LOTS of pages. There are warnings all over this page concerning the matter:
Starting Permalinks with %postname%, %category%, %tag% and %author% is strongly not recommended for performance reasons.

As I understand it, this is because Wordpress uses the same structure for the static pages you create and it can not easily distinguish between the static pages and the pages mentioned above e.g. a static page entitled "Wordpress" can have the same URL as a post with a title of "Wordpress". To correctly address this problem, Wordpress has to perform a check against each and every post in the blog.

I changed the permalink structure into this:

/p/%postname%-%monthnum%%post_id%

I knew I would lose much of my traffic but I had to do it now, before the site gets too big. Hopefully, Google and other search engines would update their indexes with my new permalinks.