That sounds like a serious bug in DD. In order to catch circularity it only needs to keep a 4 byte hash key and a short string for every reference in the structure. Unless your structure is full of almost empty arrays, hashes and scalar refs, this should take less memory than your structure.
Update: Just dug in DD and I see it's storing a 2 element arrayref for each ref it find. That's still not very much and unless you have an unusual structure, it should be negligible. The only other thing is that it stores a copy of the hash key in that 2 element array. If your keys are very big then that could be a problem however you'd still only be at most doubling things.
Update again It was a DD bug, see below