From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 15465 invoked from network); 17 Aug 2020 18:49:32 -0000 Received: from minnie.tuhs.org (45.79.103.53) by inbox.vuxu.org with ESMTPUTF8; 17 Aug 2020 18:49:32 -0000 Received: by minnie.tuhs.org (Postfix, from userid 112) id 55CEE9CAB1; Tue, 18 Aug 2020 04:49:28 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 6CFEF9DFBC; Tue, 18 Aug 2020 04:48:57 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="cJIQ8xKQ"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 385B29CAB1; Tue, 18 Aug 2020 04:48:55 +1000 (AEST) Received: from mail-vs1-f52.google.com (mail-vs1-f52.google.com [209.85.217.52]) by minnie.tuhs.org (Postfix) with ESMTPS id 58B1C9CAAF for ; Tue, 18 Aug 2020 04:48:54 +1000 (AEST) Received: by mail-vs1-f52.google.com with SMTP id o184so8819134vsc.0 for ; Mon, 17 Aug 2020 11:48:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=02D8IsuvozeLt0jHr/T3IMP4bRI7FCHuRs/PMzF8kwQ=; b=cJIQ8xKQHT2D7DeNTviJnmE52aY3QnkQrueulVXGC0Jx8WSyzzeiRCA25dkdVsVErF L5vYnnWV/oJc3C5yZPoHJVHHaMOwF3JrOpZZfvULPDfG3MFQzfBHevaWuX4O4SkZuhrL aMaKFJRzDNDqHJMAqYqnDoOCoO8PCDYrXifCBK6a74RBcRaW+EKA0re/SxPgOWcLDc1S iHbieoty3qK4jcoR49tcehN7mgHVqJGSl88uO+K8wUIr0t6IAXTmABhpeXHGEZ/ekHEz f70vJ8jNwBceEYjLl5hX+VkwCcveojuzwvriDIuaoZVPnxTAHoOLCK7UMoUBUKI87bkZ cghg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=02D8IsuvozeLt0jHr/T3IMP4bRI7FCHuRs/PMzF8kwQ=; b=t/cxt8XiV2JIwMbvpA+0F8wt1lGtHQT0Nvw4g9aLaW1uZ96ao9U+audqw2cwS8uqXg Yo2hhwD6L6mkWbbREZMSQMlT6YxlxO7zswyI/+cei8uUcMNWXGkqjSKdE9s839t3Uv2p NudwAgLQkqLJqfBSs4Ku2yWClCbeuKC/iBiVJoeG/2gKOxp7vlw59LU9EaHvIeMqo58f kZtFkXj0WXZl7EHRysvn9dbA46C79S5KHpM/fptokeJzs8uxQjd5DrZAmRJRI57C72qq atCTr2Q4fw5PzlqgIU+tQ4w99/woH838A6aiAOm74Fx1PC4+rq2dSmcLXmhks1Lf2ACU U4cQ== X-Gm-Message-State: AOAM5313JgHxcAy6tsC3CpKIruIoxVNEkc9fi6PhNnDTALQ0Drrbkm/3 GVuQvHW/m6heDbuBRZcqu38k7OZKpB9OYYqXYPQ= X-Google-Smtp-Source: ABdhPJwhlv0Azy+uXoS8YrcGw3USlh3E6RoyPU1epotal3slEuqukJJIID2vBNI2G0slnrWSTA4LjqnpZoe7q8U8R28= X-Received: by 2002:a67:68d2:: with SMTP id d201mr9196797vsc.186.1597690133315; Mon, 17 Aug 2020 11:48:53 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:ab0:48e9:0:0:0:0:0 with HTTP; Mon, 17 Aug 2020 11:48:52 -0700 (PDT) In-Reply-To: References: <20200817020224.104B518C095@mercury.lcs.mit.edu> From: Paul Winalski Date: Mon, 17 Aug 2020 14:48:52 -0400 Message-ID: To: Jim Geist Content-Type: text/plain; charset="UTF-8" Subject: Re: [TUHS] Memory management in Dennis Ritchie's C Compiler X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: The Eunuchs Hysterical Society , Noel Chiappa Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" On 8/17/20, Jim Geist wrote: > You beat me to my response. malloc/free are great for long running > processes where memory can't just infinitely increase, but there's a ton of > stuff in a compiler -- types, expressions, symbols -- that survives until > the process exits. There's benefit in both space (because you don't have to > add headers to the blocks as malloc() does, so free() can work) and time to > doing it this way. > The other issue is locality of reference. Data structures such as the symbol table get built up gradually as the compilation processes each routine. Typically the symbol table is stored as a hash table where each entry is a pointer to the actual symbol table entry data structure. If you malloc() each symbol table entry individually, they can end up scattered all over the virtual address space. It's not as important these days, when main memory is measured in gigabytes, but back when machines had less real memory, the scattering could lead to excessive page faulting. Much better to allocate symbol table entries in chunks, and the easiest way to do that is to give the symbol table its own mini-heap. VMS implemented the mini-heap concept (VMS calls them zones) back in its first release in 1978. Dave Cutler took the concept to Windows NT (Microsoft calls them private heaps). Lots of applications have built their own mini-heap system on top of sbrk(), but has a library of mini-heap-type APIs ever been distributed on Unix? -Paul W.