Embedded logic programming domain-specific languages (LP eDSLs) are software libraries allowing users to use LP in some host language without dedicated LP languages. However, all existing LP eDSLs have often extremely poor performance in comparison to dedicated LP languages. Furthermore, all are heavy on small memory allocations, and keep memory live much longer than necessary. To address these issues, we introduce a new term representation and implementation approach which piggybacks on existing host language garbage collection (GC) support for deallocation. This approach enables many optimizations, and significantly reduces the number of memory allocations performed during execution. Furthermore, our approach lets users nondeterministically construct host language data directly, avoiding LP term-based data representations if unification is unnecessary. We implement our approach in Wren: a new LP eDSL. We evaluate Wren via a benchmark suite spanning small problems to full applications, and is the largest benchmark suite ever used to evaluate an LP eDSL to the best of our knowledge. Our evaluation shows that Wren almost always outperforms the fastest-known LP eDSL, and is up 3 orders of magnitude faster, and can sometimes even surpass SWI-Prolog. We also show that Wren’s host language GC reclaims memory which would normally remain live, and allows for LP programs to run with less heap space.