This is Efficiency-of-vm_copy in view mode; [Up]
Date: Sun 17-Oct-1991 09:28:17 From: scott@gac.edu (Scott Hess) Subject: Efficiency of vm_copy() In a project I am working on, I need to manipulate some possibly vast areas of virtual memory. Data is stored as a linear array of variably-sized "chunks", in a first-in, first-out basis. Technically, I guess it's simply a first-in basis, since nothing ever really goes out ... I did it using custom memory access stuff both for space efficiency (malloc tends to leave more space than one might like for headers and tailers when you're using wildly varying data sizes), and for locality of reference. Anyhow, I've currently implemented an abstraction which works much like an array, giving access to these chunks via - access:(unsigned)elt;. It works by storing data in a linked-list of virtual memory pages, with a couple tricks I picked up from some c++ code out there to make it efficient. It has occurred to me that I could also implement this as a single large block of vm, and then when I need to expand it, I could vm_allocate then vm_copy the data to the new block, and vm_deallocate the old one. My question pertains to the implementation of vm_copy on the NeXT. Since it is constrained to copy an integral number of pages from one page boundary to another, it could conceivably be implemented by Mach magic that simply maps the copied-to area to be a copy-on-write version of the old area. Since the memory allocated by the vm_allocate call is never really allocated until I start messing with it, this would lead to a fairly efficient method to enlarge the blocks: /* The block of virtual memory. */ vm_address_t vmblock; vm_size_t vmblocksize; ... /* The new, larger block that we want. */ vm_address_t newblock; vm_size_t newblocksize; /* newblocksize>vmblocksize. */ /* Allocate the new space. */ vm_allocate( task_self(), &newblock, newblocksize, 1); /* Copy the data. */ vm_copy( task_self(), vmblock, vmblocksize, newblock); /* Deallocate the old block. */ vm_deallocate( task_self(), vmblock, vmblocksize); /* And point at the new one, now. */ vmblock=newblock; vmblocksize=newblocksize; Now, what I would like to know is if this would actually duplicate the memory, or if it would just rearrange pointers. I believe that in the best implementation of the vm_copy command (for this purpose, at least), after the vm_copy above I'll end up with newblock having the first vmblocksize/vm_page_size pages be the same pages as the original vmblock's pages. Thus, when I do the vm_deallocate, the pages are effectively transferred to the new block for good (since there will no longer be multiple copy-on-write blocks). OK, shoot at me. I'm not knowledgeable enough to really figure this out, just enough to hurt myself. There's really no reason to switch over to using a single big block over a list of smaller ones, since I've already implemented the list version. I can easily implement a parallel object using the non-list code with the same interface and drop it in as a replacement. The only memory savings to be gotten from the non-list version would amount to about 8 bytes per page - .1% savings. It's more a matter of elegance, I guess. But, if the vm_copy doesn't work as I envision above, then it becomes a matter of efficiency ... I specifically designed this to lower the amount of bcopy operations I'd do on the data (actually, I rearranged the format so bcopies weren't needed, and this popped out :-). Later,
Date: Sun 17-Oct-1991 22:27:51 From: cmaeda+@cs.cmu.edu (Christopher Maeda) Subject: Re: Efficiency of vm_copy() In article <SCOTT.91Oct17042817@tigger.jvnc.net> scott@gac.edu (Scott Hess) writes: >It has occurred to me that I could also implement this as a single >large block of vm, and then when I need to expand it, I could >vm_allocate then vm_copy the data to the new block, and vm_deallocate >the old one. My question pertains to the implementation of vm_copy >on the NeXT. Since it is constrained to copy an integral number >of pages from one page boundary to another, it could conceivably >be implemented by Mach magic that simply maps the copied-to area >to be a copy-on-write version of the old area. Since the memory >allocated by the vm_allocate call is never really allocated until >I start messing with it, this would lead to a fairly efficient >method to enlarge the blocks: Based on a quick perusal of the Mach 3.0 code (which may or may not work the same as what is on the NeXT), the vm system should work roughly as you describe; vm_copy() is essentially a page mapping operation. However, it seems like you don't need to do a copy. Why not just allocate more memory at the end of the current block whenever you need it?
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Marcel Waldvogel and Netfuture.ch.