Performance for Subbytes in AES
Fast software implementations of AES were proposed in a number of research papers. The state-of-the-art approach is to do a bitsliced implementation, where bits of sequential blocks at identical positions are processed at the same time.

The fastest implementation described so far that does not use AES-NI instructions was designed by Kasper and Schwabe. Their paper is online and is highly recommended for those who are interested in fast AES implementations. It would not make sense to copy the entire paper here, but specific questions can be answered.