If I had a friend asking me for a SEF module I will recommend to try something else. Seriously.
sh404SEF, just like other SEF url extensions, stores the SEF/non-sef url pairs in the database, and this will generate some overhead, compared to using Joomla non-sef url. It will also add overhead to Joomla own SEF urls. From our experience and testing, overhead is usually between 20 to 30%. This way of doing things however brings up some SEO benefits, which normally exceed the small time penalty incurred.
Using a disk-based cache file also reduces greatly the strain onto the DB server. On a default Joomla installation, for instance, there is virtually no database access at all on most pages, including the home page. You may want to check disk cache file is activated in your sh404sef configuration.
Having sh404SEF running on several hundreds thousands web sites has proven the performance to be a non-issue. In any case, this question is one of numbers, not just general comment such as "slow" or "fast" and you definitely want to adjust your server configuration to your requirements.
As a reference, you won't have any issue running a significant Joomla site with 1 or 2 000 visitors per day on a good $6-7/month hosting.