The executability of rewriting logic makes it a compelling environment for language design and experimentation; the ability to interpret programs directly in the language semantics develops assurance that definitions are correct and that language features work well together. However, this executability raises new questions about language semantics that don’t necessarily make sense with non-executable definitions. For instance, suddenly the performance of the semantics, not just language interpreters or compilers based on the semantics, can be important, and representations must be chosen carefully to ensure that executing programs directly in language definitions is still feasible. Unfortunately, many obvious representations common in other semantic formalisms can lead to poor performance, including those used to represent program memory. This paper describes two different memory representations designed to improve performance: the first, which has been fully developed, is designed for use in imperative programs, while the second, still being developed, is intended for use in a variety of languages, with a special focus on pure object-oriented languages. Each representation is described and compared to the initial representation used in the language semantics, with thoughts on reuse also presented.