Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


On Thu, Aug 02, 2012 at 01:32:41PM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett <josh@xxxxxxxxxxxxxxxx> wrote:
> >
> > Sorry, I should clarify what I meant: you'll have a total of one extra
> > indirection, not two.
> 
> Yes. But the hash table address generation is noticeably bigger and
> slower due to the non-fixed size too.

If you store the size as a precomputed bitmask, that should simplify the
bucket lookup to just a fetch, mask, and offset.  (You shouldn't ever
need the actual number of buckets or the shift except when resizing, so
the bitmask seems like the optimal thing to store.)  With a fixed table
size, I'd expect to see the same code minus the fetch, with an immediate
in the masking instruction.  Did GCC's generated code have worse
differences than an immediate versus a fetched value?

> In general, you can basically think of a dynamic hash table as always
> having one extra entry in the hash chains. Sure, the base address
> *may* cache well, but on the other hand, a smaller static hash table
> caches better than a big one, so you lose some and you win some.
> According to my numbers, you win a lot more than you lose.

Agreed.

I don't think any of this argues against having a second-level cache,
though, and making that one resizable seems sensible.  So, having a
scalable resizable hash table seems orthogonal to having a small
fixed-size hash table as a first-level cache.  I already agree with you
that the hash table API should not make the latter more complex or
expensive to better suit the former; as far as I can tell, address
generation seems like the only issue there.

> > Does your two-level dcache handle eviction?
> >
> > Mind posting the WIP patches?
> 
> Attached. It's against an older kernel, but I suspect it still applies
> cleanly. The patch is certainly simple, but note the warning (you can
> *run* it, though - the race is almost entirely theoretical, so you can
> get numbers without ever seeing it)
> 
>            Linus


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/


[Other Archives]     [Linux Kernel Newbies]     [Linux Driver Development]     [Linux Kbuild]     [Fedora Kernel]     [Linux Kernel Testers]     [Linux SH]     [Linux Omap]     [Linux Tape]     [Linux Input]     [Linux Kernel Janitors]     [Linux Kernel Packagers]     [Linux Doc]     [Linux Man Pages]     [Linux API]     [Linux Memory Management]     [Linux Modules]     [Linux Standards]     [Kernel Announce]     [Netdev]     [Git]     [Linux PCI]     Linux CAN Development     [Linux I2C]     [Linux RDMA]     [Linux NUMA]     [Netfilter]     [Netfilter Devel]     [SELinux]     [Bugtraq]     [FIO]     [Linux Perf Users]     [Linux Serial]     [Linux PPP]     [Linux ISDN]     [Linux Next]     [Kernel Stable Commits]     [Linux Tip Commits]     [Kernel MM Commits]     [Linux Security Module]     [AutoFS]     [Filesystem Development]     [Ext3 Filesystem]     [Linux bcache]     [Ext4 Filesystem]     [Linux BTRFS]     [Linux CEPH Filesystem]     [Linux XFS]     [XFS]     [Linux NFS]     [Linux CIFS]     [Ecryptfs]     [Linux NILFS]     [Linux Cachefs]     [Reiser FS]     [Initramfs]     [Linux FB Devel]     [Linux OpenGL]     [DRI Devel]     [Fastboot]     [Linux RT Users]     [Linux RT Stable]     [eCos]     [Corosync]     [Linux Clusters]     [LVS Devel]     [Hot Plug]     [Linux Virtualization]     [KVM]     [KVM PPC]     [KVM ia64]     [Linux Containers]     [Linux Hexagon]     [Linux Cgroups]     [Util Linux]     [Wireless]     [Linux Bluetooth]     [Bluez Devel]     [Ethernet Bridging]     [Embedded Linux]     [Barebox]     [Linux MMC]     [Linux IIO]     [Sparse]     [Smatch]     [Linux Arch]     [x86 Platform Driver]     [Linux ACPI]     [Linux IBM ACPI]     [LM Sensors]     [CPU Freq]     [Linux Power Management]     [Linmodems]     [Linux DCCP]     [Linux SCTP]     [ALSA Devel]     [Linux USB]     [Linux PA RISC]     [Linux Samsung SOC]     [MIPS Linux]     [IBM S/390 Linux]     [ARM Linux]     [ARM Kernel]     [ARM MSM]     [Tegra Devel]     [Sparc Linux]     [Linux Security]     [Linux Sound]     [Linux Media]     [Video 4 Linux]     [Linux IRDA Users]     [Linux for the blind]     [Linux RAID]     [Linux ATA RAID]     [Device Mapper]     [Linux SCSI]     [SCSI Target Devel]     [Linux SCSI Target Infrastructure]     [Linux IDE]     [Linux SMP]     [Linux AXP]     [Linux Alpha]     [Linux M68K]     [Linux ia64]     [Linux 8086]     [Linux x86_64]     [Linux Config]     [Linux Apps]     [Linux MSDOS]     [Linux X.25]     [Linux Crypto]     [DM Crypt]     [Linux Trace Users]     [Linux Btrace]     [Linux Watchdog]     [Utrace Devel]     [Linux C Programming]     [Linux Assembly]     [Dash]     [DWARVES]     [Hail Devel]     [Linux Kernel Debugger]     [Linux gcc]     [Gcc Help]     [X.Org]     [Wine]

Add to Google Powered by Linux

[Older Kernel Discussion]     [Yosemite National Park Forum]     [Large Format Photos]     [Gimp]     [Yosemite Photos]     [Stuff]