And/or-parallel system clearly suffer of the overheads coming from both and- and or-parallelism. Unfortunately, these overheads may get worse due the combination of the two forms of parallelism.
Adopting a model for exploitation of and/or-parallelism based on the layering approach, we can observe the following effects:
If stack-copying is the technique adopted to support or-parallelism, then the distributed nature of the computation makes very complicate to detect the areas that need to be transferred, making incremental copying very hard. Furthermore, and-parallelism can produce arbitrary intermixing of subgoals on the stacks, leaving trapped subgoals and empty gaps; during the copying operation, this will cause the transfer of areas which are not needed (and that will need to be properly marked as garbage).
On the other hand, if binding arrays are used to support or-parallelism, various issues related on how binding arrays are to be managed emerges and will often translates to additional overhead. If a technique like Paged Binding Arrays is used, then there will be the additional cost for managing pages and for supporting an extra level of indirection during variable access.
Furthermore, the presence of both and- and or-parallelism requires an additional scheduling step, in order to decide which form of parallelism to exploit next.
All these additional scheduling requirements can be achieved only through the use of additional data structures which collect the information required by the scheduler.