Skip to contentSkip to conversation

2.4.20-ck3 / aa / rmap with contest

BENCHMARK Con Kolivas 16 participants 100 messages Feb 9, 2003 – Feb 11, 2003

lore
Share & tools
lore
#0 lore raw

Here are a set of contest benchmarks for 2.4.20-ck3 comparing it to vanilla 2.4.20
ck3a is with the default aa vm
ck3r is with the rmap vm option

no_load:

Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 78      93.6    0.0     0.0     1.00
2420ck3a      1 78      94.9    0.0     0.0     1.00
2420ck3r      1 80      93.8    0.0     0.0     1.00
cacherun:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 74      98.6    0.0     0.0     0.95
2420ck3a      1 75      98.7    0.0     0.0     0.96
2420ck3r      1 76      97.4    0.0     0.0     0.95
process_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 123     56.1    105.0   41.5    1.58
2420ck3a      1 115     63.5    88.0    35.7    1.47
2420ck3r      1 120     61.7    94.0    35.8    1.50
ctar_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 98      79.6    2.0     5.1     1.26
2420ck3a      1 92      82.6    1.0     2.2     1.18
2420ck3r      1 97      80.4    1.0     3.1     1.21
xtar_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 130     59.2    2.0     4.6     1.67
2420ck3a      1 116     65.5    2.0     5.2     1.49
2420ck3r      1 127     60.6    2.0     3.9     1.59
io_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 297     25.3    95.5    15.5    3.81
2420ck3a      1 124     61.3    32.9    12.9    1.59
2420ck3r      1 152     51.3    35.7    12.5    1.90
io_other:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 100     74.0    32.8    15.8    1.28
2420ck3a      1 93      81.7    26.6    14.0    1.19
2420ck3r      1 110     70.0    29.7    13.6    1.38
read_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 200     39.5    16.8    5.5     2.56
2420ck3a      1 93      82.8    6.1     5.4     1.19
2420ck3r      1 121     65.3    7.2     5.0     1.51
list_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 95      78.9    0.0     5.3     1.22
2420ck3a      1 82      91.5    0.0     3.7     1.05
2420ck3r      1 94      80.9    0.0     3.2     1.18
mem_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 91      84.6    50.0    1.1     1.17
2420ck3a      1 104     73.1    51.0    1.9     1.33
2420ck3r      1 105     76.2    54.0    3.8     1.31
dbench_load:
Kernel   [runs] Time    CPU%    Loads   LCPU%   Ratio
2.4.20        1 354     21.2    4.0     38.4    4.54
2420ck3a      1 135     61.5    0.0     0.0     1.73
2420ck3r      1 180     45.0    0.0     0.0     2.25

Con

http://greetings.yahoo.com.au - Yahoo! Greetings
- Send your seasons greetings online this year!

#1 lore raw

stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

The troughput/latency curve has only a few points where the throughput incrase while latency decrease. The miniumum latency doesn't necessairly mean minimal throughput as maxmium latency doesn't necessairly imply maximal throughput.

But clearly maximum throughput likely implys not minium latency and the other way around.

I described my idea to Jens a few days ago and he's working on it right now AFIK, incidentally he had an equivalent idea in the past and he had some old code that he's starting with. For the details on how it works you can read the stochastic fair queueing in the network packet scheduler (net/sched/sch_sfq.c).

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and reordered like today since it's not latency critical. I suggeted Jens to differentiate it by checking current->mm, all the async stuff is normally submitted by the kernel daemons. A more finegrined way is to add a bitflag that you have to set between the bh lock and the submit_bh and that will be cleared by unlock_buffer (or equivalent one for the bio in 2.5). But the current->mm will take care of async-io with keventd too so it should be just fine (modulo the first aio submit but it's a minor issue).

Then the lowlevel drivers will pick requests from these queues in round robin (other variations may be possible too, like two requests per queue or stuff like that, but 1 request per queue should give an unbelieveable responsiveness to the system, something that we never experienced before).

This stochastic fair queueing I/O scheduling algorithm will be the best for desktop/multimedia, i.e. when your priority is that xmms or mplayer never skips no matter how many cp /dev/zero . you're running in background. Or also for a multiuser system. There is no other possible definitive fix IMHO. The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O. 2M of queue is the miniumum for using at best 100Mbyte arrays like my raid box.

Also the elevator-lowlatency patch right now has an unplug race that can hang the box under some workload, it's not a fatal bug (i.e. no risk of corruption and hard to trigger) and I need to fix it, like I need to limit the number of requests too or the seeking workloads get huge latencies with no throughput advantage (very well shown by tiobench in the great bigbox.html effort from Randy).

The stochastic fair queueing will allow us to keep a rasonable sized queue to avoid hurting workloads like bonnie, while still providing the maximum possible fariness across different tasks.

However it has to be optional, I suggested to use the b_max ioctl (currently unused) to select the scheduler mode, because dbench and other workloads really want the max reodering task-against-task to get the maximal throughput, not matter how long a certain dbench task is delayed. It is really up to the user to choose the I/O scheduling algorithm, just like it happens today in the network stack. Desktop users will want the stochastic fair queuing, people running workloads ala dbench must avoid it.

the stochastic fair queueing will also make the anticipatory scheduling a very low priority to have. Stochasting fair queueing will be an order of magnitude more important than anticipatory scheduling IMHO.

Andrea

#2 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

Sounds nice. I would like to see per process disk distribution.

Quoted 31 lines

The troughput/latency curve has only a few points where the throughput incrase while latency decrease. The miniumum latency doesn't necessairly mean minimal throughput as maxmium latency doesn't necessairly imply maximal throughput.

But clearly maximum throughput likely implys not minium latency and the other way around.

I described my idea to Jens a few days ago and he's working on it right now AFIK, incidentally he had an equivalent idea in the past and he had some old code that he's starting with. For the details on how it works you can read the stochastic fair queueing in the network packet scheduler (net/sched/sch_sfq.c).

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and reordered like today since it's not latency critical. I suggeted Jens to differentiate it by checking current->mm, all the async stuff is normally submitted by the kernel daemons. A more finegrined way is to add a bitflag that you have to set between the bh lock and the submit_bh and that will be cleared by unlock_buffer (or equivalent one for the bio in 2.5). But the current->mm will take care of async-io with keventd too so it should be just fine (modulo the first aio submit but it's a minor issue).

Quoted 5 lines

Then the lowlevel drivers will pick requests from these queues in round robin (other variations may be possible too, like two requests per queue or stuff like that, but 1 request per queue should give an unbelieveable responsiveness to the system, something that we never experienced before).

However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.

Quoted 14 lines

This stochastic fair queueing I/O scheduling algorithm will be the best for desktop/multimedia, i.e. when your priority is that xmms or mplayer never skips no matter how many cp /dev/zero . you're running in background. Or also for a multiuser system. There is no other possible definitive fix IMHO. The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O. 2M of queue is the miniumum for using at best 100Mbyte arrays like my raid box.

But your solution also does nothing for sequential IO throughput in the presence of more than one submitter. Two sequential readers on different parts of the disk for example. Submit 128K request (4ms), seek (5ms), submit 128K request (4ms), so your 30MB/s disk gets less than 15MB/s here. Same with writes.

I think you should be giving each process a timeslice, that way you don't need to try to account for request size or seek vs IO time and is easily tunable. This should solve the above problem with say 50ms timeslices.

It also does little to help dependant reads vs writes or streaming reads.

For reads, anticipatory scheduling can be very helpful in theory however it remains to be seen if I can make it work without adding too much complexity. Your fair queueing should go nicely on top if I can make it work. I do like your idea though!

Nick

#3 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 6 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

Sounds nice. I would like to see per process disk distribution.

Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...

Quoted 2 lines

However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.

Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...

Quoted 4 lines

But your solution also does nothing for sequential IO throughput in the presence of more than one submitter.

I think you should be giving each process a timeslice,

That is the anticipatory scheduler. A good complement to the SFQ part of the IO scheduler. I'd really like to see both ideas together in one scheduler, they sound like a winning pair.

Quoted 4 lines

For reads, anticipatory scheduling can be very helpful in theory however it remains to be seen if I can make it work without adding too much complexity. Your fair queueing should go nicely on top if I can make it work. I do like your idea though!

The anticipatory scheduler can just remain "on" while the priority difference of the requests of the current process aren't too big when compared to the priority of the other requests. Once the SFQ part of the scheduler sends down requests with a really big priority difference the anticipatory scheduler can "skip a beat" and switch to another process.

Note that Andrea's distinction between synchronous and asynchronous requests may be more appropriate than the distinction between read and write requests ...

The only remaining question is how do we know which requests are
synchronous and which are asynchronous ? Ie. which requests have
a process waiting on their completion and which requests don't have a process waiting on their completion ?

regards,

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#4 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 5 lines · Rik van Riel
Quoted 3 lines · Nick Piggin

Andrea Arcangeli wrote:

Quoted 9 lines
Quoted 5 lines
Quoted 3 lines

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

Sounds nice. I would like to see per process disk distribution.

Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...

I hope this option becomes available one day.

Quoted 6 lines
Quoted 5 lines

However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.

Quoted 6 lines

Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...

Yes, but the point is _dependant reads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.

Quoted 6 lines
Quoted 5 lines

But your solution also does nothing for sequential IO throughput in the presence of more than one submitter.

Quoted 7 lines
Quoted 2 lines

I think you should be giving each process a timeslice,

That is the anticipatory scheduler. A good complement to the SFQ part of the IO scheduler. I'd really like to see both ideas together in one scheduler, they sound like a winning pair.

No, anticipatory scheduling just "pauses for a bit after some reads" I am talking about all this nonsense about trying to measure seek vs throughput vs rotational latency, etc. We don't process schedule by how many memory accesses a process makes * processor speed / memory speed + instruction jumps.....

If you want a fair disk scheduler, just give each process a disk timeslice, and all your seek, stream, settle, track buffer, etc accounting is magically done for you... For any device, and is 100% tunable. The point is, account by _time_.

Nick

#5 lore raw

usbaudio.c 2.5.59

I am compiling 2.5.59 with the latest BK patch applied, and get the following compile error when compiling sound/usb/usbaudio.c:

sound/usb/usbaudio, in function 'create composite quirk'
warning: initialization from incompatiable pointer type, line 2219 structure has no member named 'interface' line 2226

This error did not occur in early 2.5.5X versions, but has in 2.5.59, 2.5.58 and at least a few before that.
P.S. I am testing a machine with a CMI8330 sound card and HiFi-Link usb audio device.

.config follows:
#
# Automatically generated make config: don't edit
#
CONFIG_X86=y
CONFIG_MMU=y
CONFIG_SWAP=y
CONFIG_UID16=y
CONFIG_GENERIC_ISA_DMA=y

#
# Code maturity level options
#
CONFIG_EXPERIMENTAL=y

#
# General setup
#
CONFIG_SYSVIPC=y
CONFIG_BSD_PROCESS_ACCT=y
CONFIG_SYSCTL=y
CONFIG_LOG_BUF_SHIFT=14

#
# Loadable module support
#
CONFIG_MODULES=y
CONFIG_MODULE_UNLOAD=y
# CONFIG_MODULE_FORCE_UNLOAD is not set
CONFIG_OBSOLETE_MODPARM=y
CONFIG_MODVERSIONS=y
CONFIG_KMOD=y

#
# Processor type and features
#
CONFIG_X86_PC=y
# CONFIG_X86_VOYAGER is not set
# CONFIG_X86_NUMAQ is not set
# CONFIG_X86_SUMMIT is not set
# CONFIG_X86_BIGSMP is not set
# CONFIG_M386 is not set
# CONFIG_M486 is not set
# CONFIG_M586 is not set
# CONFIG_M586TSC is not set
# CONFIG_M586MMX is not set
# CONFIG_M686 is not set
CONFIG_MPENTIUMII=y
# CONFIG_MPENTIUMIII is not set
# CONFIG_MPENTIUM4 is not set
# CONFIG_MK6 is not set
# CONFIG_MK7 is not set
# CONFIG_MK8 is not set
# CONFIG_MELAN is not set
# CONFIG_MCRUSOE is not set
# CONFIG_MWINCHIPC6 is not set
# CONFIG_MWINCHIP2 is not set
# CONFIG_MWINCHIP3D is not set
# CONFIG_MCYRIXIII is not set
CONFIG_X86_CMPXCHG=y
CONFIG_X86_XADD=y
CONFIG_X86_L1_CACHE_SHIFT=5
CONFIG_RWSEM_XCHGADD_ALGORITHM=y
CONFIG_X86_WP_WORKS_OK=y
CONFIG_X86_INVLPG=y
CONFIG_X86_BSWAP=y
CONFIG_X86_POPAD_OK=y
CONFIG_X86_TSC=y
CONFIG_X86_GOOD_APIC=y
CONFIG_X86_INTEL_USERCOPY=y
CONFIG_X86_USE_PPRO_CHECKSUM=y
# CONFIG_HUGETLB_PAGE is not set
# CONFIG_SMP is not set
CONFIG_PREEMPT=y
# CONFIG_X86_UP_APIC is not set
CONFIG_X86_MCE=y
# CONFIG_X86_MCE_NONFATAL is not set
# CONFIG_TOSHIBA is not set
# CONFIG_I8K is not set
CONFIG_MICROCODE=m
CONFIG_X86_MSR=m
CONFIG_X86_CPUID=m
# CONFIG_EDD is not set
# CONFIG_NOHIGHMEM is not set
CONFIG_HIGHMEM4G=y
# CONFIG_HIGHMEM64G is not set
CONFIG_HIGHMEM=y
# CONFIG_HIGHPTE is not set
# CONFIG_MATH_EMULATION is not set
CONFIG_MTRR=y
CONFIG_HAVE_DEC_LOCK=y

#
# Power management options (ACPI, APM)
#
CONFIG_PM=y
# CONFIG_SOFTWARE_SUSPEND is not set

#
# ACPI Support
#
# CONFIG_ACPI is not set
# CONFIG_APM is not set
# CONFIG_CPU_FREQ is not set

#
# Bus options (PCI, PCMCIA, EISA, MCA, ISA)
#
CONFIG_PCI=y
# CONFIG_PCI_GOBIOS is not set
# CONFIG_PCI_GODIRECT is not set
CONFIG_PCI_GOANY=y
CONFIG_PCI_BIOS=y
CONFIG_PCI_DIRECT=y
# CONFIG_SCx200 is not set
# CONFIG_PCI_LEGACY_PROC is not set
CONFIG_PCI_NAMES=y
CONFIG_ISA=y
# CONFIG_EISA is not set
# CONFIG_MCA is not set
CONFIG_HOTPLUG=y

#
# PCMCIA/CardBus support
#
CONFIG_PCMCIA=m
CONFIG_CARDBUS=y
CONFIG_I82092=m
CONFIG_I82365=m
# CONFIG_TCIC is not set

#
# PCI Hotplug Support
#
# CONFIG_HOTPLUG_PCI is not set

#
# Executable file formats
#
CONFIG_KCORE_ELF=y
# CONFIG_KCORE_AOUT is not set
CONFIG_BINFMT_AOUT=m
CONFIG_BINFMT_ELF=y
CONFIG_BINFMT_MISC=m

#
# Memory Technology Devices (MTD)
#
# CONFIG_MTD is not set

#
# Parallel port support
#
CONFIG_PARPORT=m
CONFIG_PARPORT_PC=m
CONFIG_PARPORT_PC_CML1=m
# CONFIG_PARPORT_SERIAL is not set
# CONFIG_PARPORT_PC_FIFO is not set
# CONFIG_PARPORT_PC_SUPERIO is not set
CONFIG_PARPORT_PC_PCMCIA=m
# CONFIG_PARPORT_OTHER is not set
CONFIG_PARPORT_1284=y

#
# Plug and Play support
#
CONFIG_PNP=y
CONFIG_PNP_NAMES=y
CONFIG_PNP_CARD=y
CONFIG_PNP_DEBUG=y

#
# Protocols
#
CONFIG_ISAPNP=y
CONFIG_PNPBIOS=y

#
# Block devices
#
CONFIG_BLK_DEV_FD=y
# CONFIG_BLK_DEV_XD is not set
# CONFIG_PARIDE is not set
# CONFIG_BLK_CPQ_DA is not set
# CONFIG_BLK_CPQ_CISS_DA is not set
# CONFIG_BLK_DEV_DAC960 is not set
CONFIG_BLK_DEV_UMEM=m
CONFIG_BLK_DEV_LOOP=y
CONFIG_BLK_DEV_NBD=m
CONFIG_BLK_DEV_RAM=y
CONFIG_BLK_DEV_RAM_SIZE=4096
CONFIG_BLK_DEV_INITRD=y
# CONFIG_LBD is not set

#
# ATA/ATAPI/MFM/RLL device support
#
CONFIG_IDE=y

#
# IDE, ATA and ATAPI Block devices
#
CONFIG_BLK_DEV_IDE=y

#
# Please see Documentation/ide.txt for help/info on IDE drives #
# CONFIG_BLK_DEV_HD_IDE is not set
# CONFIG_BLK_DEV_HD is not set CONFIG_BLK_DEV_IDEDISK=y
CONFIG_IDEDISK_MULTI_MODE=y
# CONFIG_IDEDISK_STROKE is not set CONFIG_BLK_DEV_IDECS=m
CONFIG_BLK_DEV_IDECD=y
C

#6 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Nick Piggin
Quoted 30 lines · Nick Piggin
Quoted 5 lines · Rik van Riel
Quoted 3 lines · Nick Piggin

Andrea Arcangeli wrote:

Quoted 9 lines
Quoted 5 lines
Quoted 3 lines

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

Sounds nice. I would like to see per process disk distribution.

Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...

I hope this option becomes available one day.

Quoted 6 lines
Quoted 5 lines

However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.

Quoted 6 lines

Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...

Quoted 3 lines

Yes, but the point is _dependant reads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.

note that for soem workloads the _dependant reads_ can have _dependant writes_ in between. I know it's not the most common case though, but I don't love too much to make reads that much special. But again, it makes perfect sense to have it as a feature, but I wouldn't like it to be only option, I mean there must always be a way to disable anticipatory scheduling like there must be a way to disable SFQ (infact for SFQ it makes sense to leave it disabled by default, it's only a few people that definitely only cares to have the lowest possible latency for mplayer or xmms, or for multiuser system doing lots of I/O, but those guys can't live without it)

Andrea

#7 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 54 lines · Andrea Arcangeli
Quoted 36 lines · Nick Piggin
Quoted 11 lines · Rik van Riel
Quoted 8 lines · Nick Piggin
Quoted 4 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

Quoted 7 lines
Quoted 3 lines

Sounds nice. I would like to see per process disk distribution.

Sounds like the easiest way to get that fair, indeed. Manage every disk as a separately scheduled resource...

I hope this option becomes available one day.

Quoted 5 lines
Quoted 5 lines

However dependant reads can not merge with each other obviously so you could end up say submitting 4K reads per process.

Quoted 7 lines

Considering that one medium/far disk seek counts for about 400 kB of data read/write, I suspect we'll just want to merge requests or put adjacant requests next to each other into the elevator up to a fairly large size. Probably about 1 MB for a hard disk or a cdrom, but much less for floppies, opticals, etc...

Quoted 4 lines

Yes, but the point is _dependant reads_. This is why Andrea's approach alone can't solve dependant read vs write or nondependant read - while maintaining a good throughput.

note that for soem workloads the _dependant reads_ can have _dependant writes_ in between. I know it's not the most common case though, but I don't love too much to make reads that much special. But again, it makes perfect sense to have it as a feature, but I wouldn't like it to be only option, I mean there must always be a way to disable anticipatory scheduling like there must be a way to disable SFQ (infact for SFQ it makes sense to leave it disabled by default, it's only a few people that definitely only cares to have the lowest possible latency for mplayer or xmms, or for multiuser system doing lots of I/O, but those guys can't live without it)

Quoted 2 lines

Andrea

If you pass the information down, the IO scheduler can easily put a lower expiry time on sync writes for example, or a higher one on async reads. This isn't what the anticipatory scheduler patch is about.

The point is that it is very easy to get a huge backlog of writes for the purpose of disk head schedule optimising, but this is difficult with reads, anticipatory scheduling helps address this. Thats all really.

#8 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 2 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

"The only way" ? That sounds like a lack of fantasy ;))

Having said that, I like the idea of using SFQ for fairness, since it seems to work really well for networking... I'll definately try such a patch.

Quoted 6 lines

The only other possible fix would be to reduce the I/O queue to say 512kbytes and to take advantage of the FIFO behaviour of the queue wakeups, I tried that, it works so well, you can trivially test it with my elevator-lowlatency by just changing a line, but the problem is 512k is a too small I/O pipeline, i.e. it is not enough to guarantee the maximal throughput during contigous I/O.

Maybe you want to count the I/O pipeline size in disk seeks and not in disk blocks ?

In the time of one disk seek plus half rotational latency (12 ms) you can do a pretty large amount of reading (>400kB). This means that for near and medium disk seeks you don't care all that much about how large the submitted IO is. Track buffers further reduce this importance.

OTOH, if you're seeking to the track next-door, or have mixed read and write operations on the same track, the seek time goes to near-zero and only the rotational latency counts. In that case the size of the IO does have an influence on the speed the request can be handled.

Quoted 3 lines

the stochastic fair queueing will also make the anticipatory scheduling a very low priority to have. Stochasting fair queueing will be an order of magnitude more important than anticipatory scheduling IMHO.

On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.

Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.

If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.

The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.

regards,

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#9 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 4 lines · Rik van Riel

The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.

Forget that I said that, we don't have the infrastructure to get this right. The definition of "synchronous" is "some process is waiting on this request to complete", but processes wait on other objects instead.

A normal sequence (probably the most common) is:

1) submit request
(request is now asynchronous)
2) wait_on_page
(request should now magically become synchronous)

The infrastructure to get this working is probably too big a change for 2.5/2.6, at this point, so chances are that we're better off using the (90% accurate?) distinction between reads and writes.

regards,

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#10 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

David Lang

Quoted 45 lines · Rik van Riel

Date: Mon, 10 Feb 2003 02:15:10 -0200 (BRST)
From: Rik van Riel <[email protected]>
To: Andrea Arcangeli <[email protected]>
Cc: Con Kolivas <[email protected]>, lkml <[email protected]>,
Jens Axboe <[email protected]>
Subject: Re: stochastic fair queueing in the elevator [Re: [BENCHMARK]

    2.4.20-ck3 / aa / rmap with contest]
Quoted 4 lines · Rik van Riel

The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.

Forget that I said that, we don't have the infrastructure to get this right. The definition of "synchronous" is "some process is waiting on this request to complete", but processes wait on other objects instead.

A normal sequence (probably the most common) is:

1) submit request
(request is now asynchronous)
2) wait_on_page
(request should now magically become synchronous)

The infrastructure to get this working is probably too big a change for 2.5/2.6, at this point, so chances are that we're better off using the (90% accurate?) distinction between reads and writes.

regards,

Rik
--
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/ http://guru.conectiva.com/
Current spamtrap: <a href=mailto:"[email protected]">[email protected]</a> -
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#11 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

Exactly. This is nasty with our current data structures; probably not something to do during the current code slush.

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#12 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Rik van Riel
Quoted 3 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

Exactly. This is nasty with our current data structures; probably not something to do during the current code slush.

as I said, you can consider asychronous all requests submitted with current->mm, this will be 90% accurate. This whole thing is an heuristic, if the heuristic fails the behaviour become like w/o SFQ so no regression. Also the latency of fsync is less critical than the latency of a read() syscall, again, this is statistically, sometime it can be the other way around.

Andrea

#13 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to David Lang
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

It's still approximate. An exact solution would involve only marking I/O as synchronous when some process actually waits on its completion. I do not believe that all the extra lookup and locking infrastructure and storage which this would require is justified. Certainly not in a first iteration.

The Rice Uni researchers did implement controls which attempted to learn IO submission patterns on a per-process basis, and I believe these were also used to avoid undesirable starvations. We have only briefly played with process-aware logic.

The first thing to do is to get the anticipatory scheduler working properly. Nick has been tied down for a week chasing generic bugs in the request layer. He seems to have nailed the important ones now.

#14 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

An fsync might change already submitted asynchronous writes into synchronous writes, but this is not something I'm going to lose sleep over. ;)

Quoted 4 lines

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

It's still approximate.

Sounds like a good enough approximation to me.

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#15 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 7 lines · Rik van Riel
Quoted 6 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

Quoted 6 lines
Quoted 2 lines

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

An fsync might change already submitted asynchronous writes into synchronous writes, but this is not something I'm going to lose sleep over. ;)

correct.

Quoted 7 lines
Quoted 5 lines

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

It's still approximate.

Sounds like a good enough approximation to me.

yes, the approximation should be more than enough IMHO

Andrea

#16 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 11 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Quoted 4 lines

It's still approximate. An exact solution would involve only marking I/O as synchronous when some process actually waits on its completion. I do not believe that all the extra lookup and locking infrastructure and storage which this would require is justified. Certainly not in a first iteration.

Just a quirk; NFS file servers.

The client does read-ahead - the nfsd on the server-side will wait for the read request, thus the read is synchronous... But it's not.

Signature · 6 lines
................................................................
:   [email protected]   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:
#17 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 16 lines · Jakob Oestergaard
Quoted 11 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

Quoted 8 lines

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

Nick

#18 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:
...

Quoted 8 lines
Quoted 5 lines

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

I buy the sequential-argument - very good point.

Thanks,

Quoted 3 lines

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

I'm curious as to how these things will interact in the NFS server<->client situation :)

Time will show, I guess.

Random data-point (not meant as a rant - I'm happy for all I got ;)

In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on the client) can hang for 10 seconds straight every half hour or so, when the nightly backup runs on the server (local disk reads streaming at around 2 MB/sec from an array capable of at least 40 MB/sec).

Signature · 6 lines
................................................................
:   [email protected]   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:
#19 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 5 lines · Jakob Oestergaard

In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on the

This sounds like the traditional NFS suckage that has been there for decades. The problem is that 'tar xf' ends up doing a *LOT* of NFS calls - a huge stream of stat()/open()/chmod()/utime() calls. On a local disk, most of this gets accelerated by the in-core inode cache, but on an NFS mount, you're looking at lots and lots of synchronous calls.

In 'man 5 exports':

async This option allows the NFS server to violate the NFS protocol
and reply to requests before any changes made by that request have been committed to stable storage (e.g. disc drive).

Using this option usually improves performance, but at the cost that an unclean server restart (i.e. a crash) can cause data to be lost or corrupted.

In releases of nfs-utils upto and including 1.0.0, this option
was the default. In this and future releases, sync is the
default, and async must be explicit requested if needed. To
help make system adminstrators aware of this change, 'exportfs' will issue a warning if neither sync nor async is specified.

Does this address your NFS issue?

Signature · 3 lines
				Valdis Kletnieks
				Computer Systems Senior Engineer
				Virginia Tech
#20 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 24 lines · On Mon, Feb 10, 2003 at 01:06:27AM -0500, [email protected] wrote:
Quoted 5 lines · Jakob Oestergaard

In stock 2.4.20 the interaction is horrible - whatever was done there is
not optimal. A 'tar xf' on the client will neither load the network
nor the server - it seems to be network latency bound (readahead not doing it's job - changing min-readahead and max-readahead on the client doesn't seem to make a difference). However, my desktop (running on the

This sounds like the traditional NFS suckage that has been there for decades. The problem is that 'tar xf' ends up doing a *LOT* of NFS calls - a huge stream of stat()/open()/chmod()/utime() calls. On a local disk, most of this gets accelerated by the in-core inode cache, but on an NFS mount, you're looking at lots and lots of synchronous calls.

In 'man 5 exports':

async This option allows the NFS server to violate the NFS protocol
and reply to requests before any changes made by that request have been committed to stable storage (e.g. disc drive).

Using this option usually improves performance, but at the cost that an unclean server restart (i.e. a crash) can cause data to be lost or corrupted.

Quoted 7 lines

In releases of nfs-utils upto and including 1.0.0, this option
was the default. In this and future releases, sync is the
default, and async must be explicit requested if needed. To
help make system adminstrators aware of this change, 'exportfs' will issue a warning if neither sync nor async is specified.

Does this address your NFS issue?

No. Tried it in the past, just tried it again to make sure.

The caching should be done client-side, I guess, to be effective. Even if the server acknowledges operations before they hit the disks, the client is still bound by the RPC call latency.

I'm sure there are problems preventing such caching... Hmm... Seems
like the only way out is a multi-threaded tar ;) Or tar using AIO.

Btw. nocto on the client doesn't really seem to help matters much either.

Thanks for the suggestion,

Signature · 6 lines
................................................................
:   [email protected]   : And I see the elder races,         :
:.........................: putrid forms of man                :
:   Jakob Østergaard      : See him rise and claim the earth,  :
:        OZ9ABN           : his downfall is at hand.           :
:.........................:............{Konkhra}...............:
#21 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Nick Piggin
Quoted 28 lines · Nick Piggin
Quoted 18 lines · Jakob Oestergaard
Quoted 7 lines · Andrew Morton
Quoted 5 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous'
as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

Quoted 6 lines

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

Quoted 8 lines

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Quoted 7 lines

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.

Andrea

#22 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 37 lines · Andrea Arcangeli
Quoted 35 lines · Nick Piggin
Quoted 19 lines · Jakob Oestergaard
Quoted 8 lines · Andrew Morton
Quoted 5 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

Quoted 6 lines

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

Quoted 9 lines

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Quoted 9 lines
Quoted 4 lines

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.

You seem to be forgetting things like seek time.

#23 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 47 lines · Nick Piggin
Quoted 45 lines · Andrea Arcangeli
Quoted 42 lines · Nick Piggin
Quoted 22 lines · Jakob Oestergaard
Quoted 10 lines · Andrew Morton
Quoted 7 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous'
as should writes to any partition mounted with the sync option, or writes
to a directory with the S flag set.

Quoted 7 lines

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

Quoted 9 lines

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

Quoted 5 lines
Quoted 4 lines

the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.

You seem to be forgetting things like seek time.

I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Andrea

#24 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 5 lines · Andrea Arcangeli

BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.

And neither fs performs inode table readahead.

#25 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli

BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.

At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.

Andrea

#26 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 12 lines · Andrea Arcangeli
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli

BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.

Quoted 8 lines

At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.

No, it's doing the directory readahead against the correct blocks (it calls ext3_getblk() to find them).

Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.

#27 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 22 lines · Andrew Morton
Quoted 12 lines · Andrea Arcangeli
Quoted 9 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli

BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.

Quoted 8 lines

At least for big directories it should be at least a quite obvious microoptimization, if you do it at the logical level. Maybe it wasn't worthwhile in the past (like in ext3) because it was done at the block layer with a dumb reada rather than with proper read of the next logical block before wait_on_buffer. Also keep in mind the max readahead generated by the block layer is nothing compared to the true readahead that the logical layer is able to generate.

Quoted 2 lines

No, it's doing the directory readahead against the correct blocks (it calls ext3_getblk() to find them).

yes, sorry.

Andrea

#28 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 6 lines · Andrew Morton

Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.

Quoted 9 lines

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

readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.

Signature · 1 line
Hans
#29 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 18 lines · Hans Reiser
Quoted 7 lines · Andrew Morton

Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.

Quoted 9 lines

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

Quoted 1 line

readahead seems to be less effective for non-sequential objects. Or at

yes, this is why I said readahead matters mostly to generate the big dma commands, so if the object is sequential it will be served by the lowlevel with a single dma using SG. this is also why when I moved the high dma limit of scsi to 512k (from 128k IIRC) I got such a relevant throughput improvement. Also watch the read speed in my tree compared to 2.4 and 2.5 in bigbox.html from Randy (bonnie shows it well).

Quoted 3 lines

least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

Agreed.

Andrea

#30 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 23 lines · Andrea Arcangeli
Quoted 18 lines · Hans Reiser
Quoted 5 lines · Andrew Morton

Large directories tend to be spread all around the disk anyway. And I've never explicitly tested for any problems which the loss of readahead might have caused ext2. Nor have I tested inode table readahead. Guess I should.

Quoted 10 lines

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

Quoted 2 lines

readahead seems to be less effective for non-sequential objects. Or at

Quoted 7 lines

yes, this is why I said readahead matters mostly to generate the bigdma commands, so if the object is sequential it will be served by the lowlevel with a single dma using SG. this is also why when I moved the high dma limit of scsi to 512k (from 128k IIRC) I got such a relevant throughput improvement. Also watch the read speed in my tree compared to 2.4 and 2.5 in bigbox.html from Randy (bonnie shows it well).

...AND readahead matters mostly to disk head scheduling when there is other IO competing with the streaming read...

A big throughput improvement would have seen would be all to do with better disk head scheduling due to the larger request sizes, yeah? And this would probably be to do with the elevator accounting being based on requests and/or seeks. You shouldn't notice much difference with the elevator stuff in Andrew's mm patches.

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

Nick

#31 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

Andrea

#32 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

Quoted 8 lines

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

I thought scsi in 2.5 was doing 512k I/O's at present???

Doesn't Randy attribute the differences there to an updated
qlogic driver? (Or was the update to allow 512k I/O's? ;))

#33 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 16 lines · Andrew Morton
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

Quoted 8 lines

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

Quoted 4 lines

I thought scsi in 2.5 was doing 512k I/O's at present???

Doesn't Randy attribute the differences there to an updated
qlogic driver? (Or was the update to allow 512k I/O's? ;))

The special case of the qlogic that Randy is using does 256k commands with the new driver.

Andrea

#34 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

Quoted 8 lines

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire overhead of using small requests does not seem to be it.

Nick

#35 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 17 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

Quoted 8 lines

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

Quoted 2 lines

Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about

correct, that's the huge improvement I get in the read sequential case (i.e. bonnie), which is a crucial common workload.

Quoted 3 lines

SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

writes don't need readahead to use the max command size, they always used it since the first place, so they can't go even faster, they never had a problem.

It's by fixing readahead that reads gets boosted. this has nothing to do with writes or the max_sectors itself.

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

Quoted 4 lines

overhead of using small requests does not seem to be it.

Nick

Andrea

#36 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 22 lines · Andrea Arcangeli
Quoted 20 lines · Nick Piggin
Quoted 17 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin

I don't know too much about SCSI stuff, but if driver / wire / device overheads were that much higher at 128K compared to 512K I would think something is broken or maybe optimised badly.

I guess it's also a matter of the way the harddisk can serve the I/O if it sees it all at the same time, not only the cpu/bus protocol after all minor overhead. Most certainly it's not a software mistake in linux that the big commands runs that much faster. Again go check the numbers in bigbox.html between my tree, 2.4 and 2.5 in bonnie read sequential, to see the difference between 128k commands and 512k commands with reads, these are facts. (and no writes and no seeks here)

Quoted 7 lines
Quoted 3 lines

Yes it is very clear from the numbers that your tree is more than 150% the speed for reads. As I said I don't know too much about

correct, that's the huge improvement I get in the read sequential case (i.e. bonnie), which is a crucial common workload.

Yep

Quoted 7 lines
Quoted 6 lines

SCSI, but it is very interesting that writes don't get a noticable improvement although they would be using the bigger request sizes too, right? Something is causing this but the cpu, bus, wire

Quoted 8 lines

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

writes don't need readahead to use the max command size, they always used it since the first place, so they can't go even faster, they never had a problem.

Yes I am an idiot, I don't know why I said that :P

Quoted 10 lines

It's by fixing readahead that reads gets boosted. this has nothing to do with writes or the max_sectors itself.

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

Look at the few simple tests I have been posting - it clearly indicates the need is decreased. I did say however that it would be subject to CPU/bus/device overheads. I did not realiase SCSI setups would behave like this. From a purely disk head perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).

#37 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 2 lines · Nick Piggin

perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).

I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.

NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.

Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.

Andrea

#38 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).

Quoted 8 lines

I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.

I don't understand it at all. I mean there is no other IO going on so there would be no reason for the disk head to move anyway. Rotational latency should be basically non-existant due to track buffers, and being FC RAID hardware you wouldn't expect them to skimp on anything.

Quoted 9 lines

NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.

Yes it definately has to be selectable (in fact, in my current version, setting antic_expire = 0 disables it), and Andrew has been working on tuning the non anticipatory version into shape.

Quoted 13 lines

Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.

It would be easy to anticipate or not based on hints. We could anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).

#39 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 16 lines · Nick Piggin
Quoted 6 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).

Quoted 8 lines

I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things and to keep the head at the right place for longer, dunno. Anyways, whatever is the reason it doesn't make much difference from our point of view ;), but I don't expect this hardware behaviour changing in future high end storage.

Quoted 1 line

I don't understand it at all. I mean there is no other IO going

Unfortunately I can't help you understand it, but this is what I found with my pratical experience, I found it the first time in my alpha years ago when I increased the sym to 512k in early 2.4 then since it could break stuff we added the max_sectors again in 2.4. But of course if you don't fix readahead there's no way reads can take advantage of these lowlevel fixes. I thought I fixed readahead too but I felt it got backed out and when I noticed I resurrected it in my tree (see the name of the patch ;)

Quoted 10 lines
Quoted 7 lines

NOTE: just to be sure, I'm not at all against anticpiatory scheduling, it's clearly a very good feature to have (still I would like an option to disable it especially in heavy async environments like databases, where lots of writes are sync too) but it should be probably be enabled by default, especially for the metadata reads that have to be synchronous by design.

Yes it definately has to be selectable (in fact, in my current version, setting antic_expire = 0 disables it), and Andrew has been working on tuning the non anticipatory version into shape.

Great.

Quoted 11 lines
Quoted 11 lines

Infact I wonder that it may be interesting to also make it optionally controlled from a fs hint (of course we don't pretend all fs to provide the hint), so that you stall I/O writes only when you know for sure you're going to submit another read in a few usec, just the time to parse the last metadata you read. Still a timeout would be needed for scheduling against RT etc..., but it could be a much more relaxed timeout with this option enabled, so it would need less accurate timings, and it would be less dependent on hardware, and it would be less prone to generate false positive stalls. The downside is having to add the hints.

Quoted 1 line

It would be easy to anticipate or not based on hints. We could

yep.

Quoted 3 lines

anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).

this is not the way I thought at it. I'm interested to give an hint only to know for sure which are the intermediate sync dependent reads (the obvious example is when doing the get_block and walking the 3 level of inode indirect metadata blocks with big files, or while walking the balanced tree in reiserfs), and I'm not interested at all about writes. And I would just set an higher timeout when a read that I know for sure (thanks to the hint) is "intermdiate" is completed. We can use high timeouts there because we know they won't trigger 90% of the time, a new dependent read will be always submitted first.

Andrea

#40 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 5 lines · Andrea Arcangeli
Quoted 2 lines · Nick Piggin

I don't understand it at all. I mean there is no other IO going

Quoted 9 lines

Unfortunately I can't help you understand it, but this is what I found with my pratical experience, I found it the first time in my alpha years ago when I increased the sym to 512k in early 2.4 then since it could break stuff we added the max_sectors again in 2.4. But of course if you don't fix readahead there's no way reads can take advantage of these lowlevel fixes. I thought I fixed readahead too but I felt it got backed out and when I noticed I resurrected it in my tree (see the name of the patch ;)

Fair enough. I accept it is important. Still think its odd ;)

[snip]

Quoted 11 lines
Quoted 2 lines

It would be easy to anticipate or not based on hints. We could

yep.

Quoted 4 lines

anticipate sync writes if we wanted, lower expire time for sync writes, increase it for async reads. It is really not very complex (although the code needs tidying up).

Quoted 10 lines

this is not the way I thought at it. I'm interested to give an hint only to know for sure which are the intermediate sync dependent reads (the obvious example is when doing the get_block and walking the 3 level of inode indirect metadata blocks with big files, or while walking the balanced tree in reiserfs), and I'm not interested at all about writes. And I would just set an higher timeout when a read that I know for sure (thanks to the hint) is "intermdiate" is completed. We can use high timeouts there because we know they won't trigger 90% of the time, a new dependent read will be always submitted first.

This is a lot of nitty gritty stuff. It will all help, especially in corner cases. Luckily it seems you don't need such infrastructure to demonstrate most anticipatory scheduler gains.

#41 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 2 lines · Nick Piggin

in corner cases. Luckily it seems you don't need such infrastructure to demonstrate most anticipatory scheduler gains.

sure. I guess it would be most important to be allowed to leave anticipatory scheduling enabled *always* even with very async-io intensive workloads, so when you read a file with normal fileutiles you still can take advantage of it for the most important places. Ideally in this case where w/o the hint we might have to disable anticipatory scheduling completely to get peak async-io performance, the non-hint timeout could be zero (i.e. no stall at all) and the kernel would understand and do the right thing

Andrea

#42 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 9 lines · Andrea Arcangeli
Quoted 2 lines · Nick Piggin

perspective it does nullify the need for readahead (though it is obivously still needed for other reasons).

I'm guessing that physically it may be needed from a head prospective too, I doubt it only has to do with the in-core overhead. Seeing it all before reaching the seek point might allow the disk to do smarter things

NOTE: just to be sure, I'm not at all against anticpiatory scheduling,

Most disks seem to have a large cache, but with the cache unit for most of the cache being one _track_ at a time.

This has the effect of the disk reading one track in at a time, but only being able to cache a few of these tracks in its cache.

Anticipatory scheduling should reduce any thrashing of this disk cache.

regards,

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#43 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

- *max_ra++ = vm_max_readahead;
+ *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

Quoted 5 lines

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.

#44 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 4 lines

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

Though Andrea did say it is a "single threaded" streaming read. That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.

#45 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 15 lines · Nick Piggin
Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 5 lines
Quoted 4 lines

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

Though Andrea did say it is a "single threaded" streaming read.

yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.

Andrea

#46 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 24 lines · Andrea Arcangeli
Quoted 22 lines · Nick Piggin
Quoted 19 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

Quoted 6 lines
Quoted 2 lines

Though Andrea did say it is a "single threaded" streaming read.

yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.

The same pattern is also observed with single threaded tiobench anyway.

#47 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 27 lines · Nick Piggin
Quoted 25 lines · Andrea Arcangeli
Quoted 23 lines · Nick Piggin
Quoted 20 lines · Andrew Morton
Quoted 5 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;

Well of course that will get bigger bonnie numbers, for exactly the reasons
I've explained. It will seek between files after every 512k rather than after every 128k.

Quoted 8 lines
Quoted 6 lines
Quoted 2 lines

Though Andrea did say it is a "single threaded" streaming read.

yes, I pointed you to bonnie read sequential in bigbox.html, not tiobench.

The same pattern is also observed with single threaded tiobench anyway.

yes, of course.

Andrea

#48 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Nick Piggin
Quoted 16 lines · Nick Piggin
Quoted 13 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 5 lines
Quoted 4 lines

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

Though Andrea did say it is a "single threaded" streaming read.

Oh sorry, I missed that.

Quoted 6 lines

That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.

Yes, that's a bit odd. Some reduction in CPU cost and bus
traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.

#49 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · Andrew Morton

traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.

I'm guessing something on those lines yes, I doubt it's purerely in core overhead that makes that much difference. Just for completeness, I never read this in literature or data sheets, this is all out of pratical experience, so we can't exclude something odd in the scsi layer, but I very much doubt, the only thing that might explain it is to waste cpu and we know it's not wasting it.

Andrea

#50 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 10 lines · Andrew Morton
Quoted 7 lines · Nick Piggin

That is what I can't understand. Movement of the disk head should be exactly the same in either situation and 128K is not exactly a pitiful request size - so it suggests a quirk somewhere. It is not as if the disk has to be particularly smart or know a lot about the data in order to optimise the head movement for a load like this.

Quoted 5 lines

Yes, that's a bit odd. Some reduction in CPU cost and bus
traffic, etc would be expected. Could be that sending out a
request which is larger than a track is saving a rev of the disk for some reason.

Shouldn't be. Even at 128KB readahead we should always have outstanding requests against the disk in a streaming read scenario, right? Maybe if the track buffers are bigger than 128K?

Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?

#51 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 2 lines · Nick Piggin

Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?

I recall more than 512k wasn't worthwhile anymore

Andrea

#52 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?

I recall more than 512k wasn't worthwhile anymore

Behaviour between 128 and 512 would be interesting then

#53 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 11 lines · Nick Piggin
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · Nick Piggin

Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?

I recall more than 512k wasn't worthwhile anymore

Behaviour between 128 and 512 would be interesting then

this is exactly what is shown by Randy's bonnie ;)

Andrea

#54 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 20 lines · Andrea Arcangeli
Quoted 17 lines · Nick Piggin
Quoted 13 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin

Is there a magic number above which you see the improvement, Andrea? Or does it steadily climb?

I recall more than 512k wasn't worthwhile anymore

Quoted 6 lines
Quoted 3 lines

Behaviour between 128 and 512 would be interesting then

this is exactly what is shown by Randy's bonnie ;)

I don't see it... I mean eg 192, 256, 320...

#55 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 2 lines · Andrew Morton

Could be that sending out a request which is larger than a track is saving a rev of the disk for some reason.

I guess disks are optimised for the benchmarks that are run by popular PC magazines ...

After all, those benchmarks and the sales price are the main factors determining sales ;)

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#56 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 7 lines · ext Rik van Riel
Quoted 2 lines · Andrew Morton

Could be that sending out a request which is larger than a track is saving a rev of the disk for some reason.

I guess disks are optimised for the benchmarks that are run by popular PC magazines ...

Yes, absolutely they are (I used to work for one such company that no longer exists). However, there's a catch -- the disk drive companies are optimizing for the test as currently constituted, but the test keeps changing. So they're optimizing for version N-1 while the magazine is publishing N. Can't help it. Ever heard of the Nyquist frequency?

Quoted 4 lines

After all, those benchmarks and the sales price are the main factors determining sales ;)

Yup. In general, it's capacity first, then reliability, then performance. No, wait, not quite; the FIRST criterion is the ability to ship when you say you will. If you make Dell late on shipping a bunch of machines, you WILL feel the pain.

		--Rod
#57 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 12 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 3 lines

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.

Second I increased it to 4 times 128k very recently, it was used to be exactly 128k and 512k for scsi. Infact the difference happens in SCSI not IDE, where going past 128k is helpful, on ide as said the limit of the command is limited by the hardware anyways.

the only thing you can argue is that the qla is capable of max 256k per command, and I'm doing readahead of 512k at once, but I don't think it can matter, like it doesn't matter now that I increased it even more, all it matters is not to stop at 128k, and to submit the 256k commands.

Quoted 10 lines
Quoted 6 lines

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.

This has nothing to do with "the other file". There is a single task in the system, it is in replacement of /sbin/init, it never forks and it never opens more than 1 single file called /myfile. Nothing else nothing more.

anticipatory scheduling can't help in any way that benchmark, period. If you destroy readahead you won't be able to build the scsi command of the optimal size and this will hurt. Waiting can't help this.

Andrea

#58 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 14 lines · Andrea Arcangeli
Quoted 12 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;
Quoted 9 lines
Quoted 4 lines

Well of course that will get bigger bonnie numbers, for exactly the reasons I've explained. It will seek between files after every 512k rather than after every 128k.

NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.

Yes, Andrew obviously missed this... Anyway, could it be due to a big stripe size and hitting more disks in the RAID? How does a single SCSI disk perform here, Andrea?

#59 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 22 lines · Nick Piggin
Quoted 20 lines · Andrea Arcangeli
Quoted 17 lines · Andrew Morton
Quoted 4 lines · Andrea Arcangeli

It's the readahead in my tree that allows the reads to use the max scsi command size. It has nothing to do with the max scsi command size itself.

Oh bah.

(quoted diff) +1 -1
-               *max_ra++ = vm_max_readahead;
+               *max_ra = ((128*4) >> (PAGE_SHIFT - 10)) - 1;

Well of course that will get bigger bonnie numbers, for exactly the reasons
I've explained. It will seek between files after every 512k rather than after every 128k.

Quoted 7 lines
Quoted 4 lines

NOTE: first there is no seek at all in the benchmark we're talking about, no idea why you think there are seeks. This is not tiobench, this is bonnie sequential read.

Yes, Andrew obviously missed this... Anyway, could it be due to a big stripe size and hitting more disks in the RAID? How does a single SCSI disk perform here, Andrea?

Actually I increased readahead to more than just 512k in my last tree, especially to take care of RAID :) so that both lowlevel will get the 512k, instead of being limited to 256k command each 8) This might apply to hardware raid too.

Andrea

#60 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli

Is the following a fair summary?

There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.

Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.

Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.

Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).

Is this a fair summary?

Signature · 1 line
Hans
#61 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 14 lines · Hans Reiser

Is the following a fair summary?

There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.

Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.

Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.

Quoted 5 lines

Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).

Is this a fair summary?

I would also add what I feel the most important thing, that is anticipatory scheduling can help decreasing a lot the latencies of filesystem reads in presence of lots of misc I/O, by knowing which are the read commands that are intermediate-dependent-sync, that means knowing a new dependent read will be submitted very quickly as soon as the current read-I/O is completed. In such a case it makes lots sense to wait for the next read to be submitted instead of start processing immediatly the rest of the I/O queue. This way when you read a file and you've to walk the indirect blocks before being able to read the data, you won't be greatly peanalized against the writes or reads that won't need to pass through metadata I/O before being served.

This doesn't obviate the need of SFQ for the patological multimedia cases where I/O latency is the first prio, or for workloads where sync-write latency is the first prio.

BTW, I'm also thinking that the SFQ could be selected not system wide, but per-process basis, with a prctl or something, so you could have all the I/O going into the single default async-io queue, except for mplayer that will use the SFQ queues. This may not even need to be privilegied since SFQ is fair and if an user can write a lot it can just hurt latency, with SFQ could hurt more but still not deadlock. This SFQ prctl for the I/O scheduler, would be very similar to the RT policy for the main process scheduler. Infact it maybe the best to just have SFQ always enabled, and selectable only via the SFQ prctl, and to enable the functionaltiy only per-process basis rather than global. We can still add a sysctl to enable it globally despite nobody set the per-process flag.

Andrea

#62 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 17 lines · Andrea Arcangeli
Quoted 4 lines · Hans Reiser

Is the following a fair summary?

There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.

Quoted 9 lines

Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.

Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.

Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).

Is this a fair summary?

Quoted 7 lines

I would also add what I feel the most important thing, that is anticipatory scheduling can help decreasing a lot the latencies of filesystem reads in presence of lots of misc I/O, by knowing which are the read commands that are intermediate-dependent-sync, that means knowing a new dependent read will be submitted very quickly as soon as the current read-I/O is completed.

Ah.... yes... I have seen that be a problem, and reiserfs suffers from it more than ext2....

maybe we should simply have an explicit protocol for that... I would be quite willing to have reiserfs use some flag that says WILL_READ_NEARBY_NEXT whenever it reads an internal node to get the location of its children.... that might be a lot cleaner than trying to do it all in your layer... what do you guys think...

Perhaps it will be both less code, and a better result in that it avoids some unnecessary lingering....

Quoted 24 lines

In such a case it makes lots sense to
wait for the next read to be submitted instead of start processing immediatly the rest of the I/O queue. This way when you read a file and you've to walk the indirect blocks before being able to read the data, you won't be greatly peanalized against the writes or reads that won't need to pass through metadata I/O before being served.

This doesn't obviate the need of SFQ for the patological multimedia cases where I/O latency is the first prio, or for workloads where sync-write latency is the first prio.

BTW, I'm also thinking that the SFQ could be selected not system wide, but per-process basis, with a prctl or something, so you could have all the I/O going into the single default async-io queue, except for mplayer that will use the SFQ queues. This may not even need to be privilegied since SFQ is fair and if an user can write a lot it can just hurt latency, with SFQ could hurt more but still not deadlock. This SFQ prctl for the I/O scheduler, would be very similar to the RT policy for the main process scheduler. Infact it maybe the best to just have SFQ always enabled, and selectable only via the SFQ prctl, and to enable the functionaltiy only per-process basis rather than global. We can still add a sysctl to enable it globally despite nobody set the per-process flag.

Quoted 5 lines

Andrea

I still don't really understand your SFQ design, probably because I haven't studied recent networking algorithms that your description assumed I understand.

Signature · 1 line
Hans
#63 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Hans Reiser
Quoted 3 lines · Hans Reiser

Is the following a fair summary?

There is a certain minimum size required for the IOs to be cost effective. This can be determined by single reader benchmarking. Only readahead and not anticipatory scheduling addresses that.

Well as a rule you would gain efficiency the larger your request size gets. There will be a point where you make the trade off. And no, anticipatory scheduling will not make read request sizes bigger.

Quoted 3 lines

Anticipatory scheduling does not address the application that spends one minute processing every read that it makes. Readahead does.

In the presence of other IO, anticipatory scheduling would help here. In the absense of other IO, readahead would not help (past the efficiency problem above). However anticipatory scheduling _would_ mean you don't need as much RAM tied up doing nothing (or being discarded) for one minute before it is needed.

Quoted 3 lines

Anticipatory scheduling does address the application that reads multiple files that are near each other (because they are in the same directory), and current readahead implementations (excepting reiser4 in progress vaporware) do not.

File readahead would not help. Anticipatory scheduling can.

Quoted 3 lines

Anticipatory scheduling can do a better job of avoiding unnecessary reads for workloads with small time gaps between reads than readahead (it is potentially more accurate for some workloads).

It avoids seeks mainly, but the lesser need for readahead should mean the readahead algorithm doesn't need to be very smart.

Quoted 3 lines

Is this a fair summary?

Well I don't see it so much as readahead vs anticipatory scheduling. I know readahead is important.

#64 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.

In reply to Andrew Morton
Quoted 10 lines
Quoted 6 lines

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.

IMHO anticipatory scheduling and readahead address different problems. RA is simpler and cheaper. Reading a few more KB comes almost for free and that helps a lot sequential reads. AS is useful for random i/o (fs metadata, executables, ...), but it wastes time if the timer expires, or if the new request wants data which is far away the previous one. AS is useful for sequential reads too, but only if the application reads large chunks of data, otherwise RA is better. I we need both RA and AS to address the largest variety of workloads.

Bye.

#65 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.

Quoted 11 lines · Giuliano Pochini
Quoted 10 lines
Quoted 6 lines

You can wait 10 minutes and still such command can't grow. This is why claiming anticipatory scheduling can decrease the need for readahead doesn't make much sense to me, there are important things you just can't achieve by only waiting.

The anticipatory scheduler can easily permit 512k of reading before seeking away to another file. In fact it can allow much more, without requiring that readhead be cranked up.

Quoted 5 lines

IMHO anticipatory scheduling and readahead address different problems. RA is simpler and cheaper. Reading a few more KB comes almost for free and that helps a lot sequential reads. AS is useful for random i/o (fs metadata, executables, ...), but it wastes time if the timer expires, or if the new request wants data which is far away the previous one. AS is useful for

Yep.

Quoted 2 lines

sequential reads too, but only if the application reads large chunks of data, otherwise RA is better. I we need both RA and AS to address the

actually even if the app reads large chunks of data RA is needed, the size of the read/io_submit syscalls won't reach the readpage/wait_on_page at the pagecache layer, w/o readahead we would read PAGE_SIZE per dma and not more (ignoring PAGE_CACHE_SIZE of course, which isn't going to be enough anyways due mem fragmentation issues)

Quoted 3 lines

largest variety of workloads.

Bye.

Andrea

#67 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · Hans Reiser

Is it true that there is no manpage available anywhere for fadvise?

It's pretty simple.

http://www.opengroup.org/onlinepubs/007904975/functions/posix_fadvise.html

It's also basically unimplementable without the radix tree, so I don't how other systems can be doing it. Maybe they just lock up for a day when someone does fadvise64(fd, 0, -1, FADV_DONTNEED) ;)

#68 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Andrew Morton
Quoted 4 lines · Hans Reiser

Is it true that there is no manpage available anywhere for fadvise?

Quoted 12 lines

It's pretty simple.

http://www.opengroup.org/onlinepubs/007904975/functions/posix_fadvise.html

It's also basically unimplementable without the radix tree, so I don't how other systems can be doing it. Maybe they just lock up for a day when someone does fadvise64(fd, 0, -1, FADV_DONTNEED) ;)

Andrew, don't you think you should write a linux manpage and/or other documentation when you add system calls like fadvise to linux? Also, Andrew, your measurements would be a lot more understandable if you did not use programs written by you and not present in any linux distro (do I understand that correctly?) without defining what they do. Yes? ;-)

Signature · 1 line
Hans
#69 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Hans Reiser
Quoted 6 lines · Hans Reiser

readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

Quoted 6 lines

For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.

The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.

Readahead is brute force. The anticipatory scheduler solves this in a smarter way.

Yes, device readahead helps. But I believe the caches are only 4-way segmented or thereabouts, so it is easy to thrash them. Let's test:

vmm:/mnt/hda6> dd if=/dev/zero of=file1 bs=1M count=100 100+0 records in
100+0 records out
vmm:/mnt/hda6> dd if=/dev/zero of=file2 bs=1M count=100 100+0 records in
100+0 records out
vmm:/mnt/hda6> fadvise file1 0 9999999999 dontneed vmm:/mnt/hda6> fadvise file2 0 9999999999 dontneed vmm:/mnt/hda6> time cat file1 > /dev/null & time cat file2 > /dev/null cat 2 > /dev/null 0.00s user 0.11s system 0% cpu 21.011 total cat 1 > /dev/null 0.00s user 0.14s system 0% cpu 23.011 total vmm:/mnt/hda6> 0 blockdev --setra 4 /dev/hda
vmm:/mnt/hda6> fadvise file1 0 9999999999 dontneed vmm:/mnt/hda6> fadvise file2 0 9999999999 dontneed vmm:/mnt/hda6> time cat file1 > /dev/null & time cat file2 > /dev/null cat 2 > /dev/null 0.07s user 0.43s system 1% cpu 31.431 total cat 1 > /dev/null 0.01s user 0.27s system 0% cpu 31.430 total

OK, so there's a 50% slowdown on a modern IDE disk from not using readahead.

vmm:/mnt/hda6> for i in $(seq 1 8)
for> do
for> dd if=/dev/zero of=file$i bs=1M count=10
for> sync
for> fadvise file$i 0 999999999 dontneed
for> done

vmm:/home/akpm> 0 blockdev --setra 240 /dev/hda1
for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done

cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 4.422 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 5.801 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.012 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.261 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 6.401 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.494 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.754 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.757 total

vmm:/mnt/hda6> for i in $(seq 1 8)
do
fadvise file$i 0 999999999 dontneed
done
vmm:/home/akpm> 0 blockdev --setra 4 /dev/hda1
vmm:/mnt/hda6> for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done

cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 13.373 total
cat file$i > /dev/null  0.00s user 0.04s system 0% cpu 14.849 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 15.816 total
cat file$i > /dev/null  0.00s user 0.04s system 0% cpu 16.808 total
cat file$i > /dev/null  0.00s user 0.05s system 0% cpu 17.824 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.004 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.274 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.301 total

So with eight files, it's a 300% drop from not using readahead.

With 16 files, readahead enabled:

cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 9.887 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 10.925 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 11.033 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 11.146 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 11.381 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 11.640 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 11.907 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 12.262 total

....

Readahead disabled:

cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 39.307 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 39.378 total
cat file$i > /dev/null  0.00s user 0.04s system 0% cpu 39.679 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 39.888 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 40.261 total

Still only 300%. I'd expect to see much larger differences on some older SCSI disks I have here.

#70 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 13 lines · Andrew Morton
Quoted 5 lines · Hans Reiser

readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.

The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.

Quoted 6 lines

Readahead is brute force. The anticipatory scheduler solves this in a smarter way.

Yes, device readahead helps. But I believe the caches are only 4-way segmented or thereabouts, so it is easy to thrash them. Let's test:

[snip results]

Quoted 5 lines

Still only 300%. I'd expect to see much larger differences on some older SCSI disks I have here.

It would be interesting to see numbers with and without anticipatory scheduling as well. I have tried two streaming readers. Speed with default readahead 13MB/s
Speed with no readahead, no anticipation 7MB/s
Speed with no readahead, anticipation 11.8MB/s

I suspect more readers will simply favour the anticipatory scheduler more.

Nick

#71 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 14 lines · Andrew Morton
Quoted 6 lines · Hans Reiser

readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

Quoted 6 lines

For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.

Quoted 4 lines

The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.

definitely, but again the most important by far is to submit big commands, if you get the 512k commands interleaved by different task it isn't a panic situation.

Quoted 2 lines

Readahead is brute force. The anticipatory scheduler solves this in a smarter way.

If you decrease readahead with anticipatory scheduler you will submit the small commands, if you decrease the readahead you can stall 10 minutes any write in the queue, and still you won't grow the command in the head of the queue.

Quoted 5 lines

vmm:/mnt/hda6> for i in $(seq 1 8)
for> do
for> dd if=/dev/zero of=file$i bs=1M count=10
for> sync
for> fadvise file$i 0 999999999 dontneed

what is this fadvise doing?

Quoted 35 lines

for> done

vmm:/home/akpm> 0 blockdev --setra 240 /dev/hda1

for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done

cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 4.422 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 5.801 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.012 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.261 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 6.401 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.494 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.754 total
cat file$i > /dev/null  0.00s user 0.01s system 0% cpu 6.757 total

vmm:/mnt/hda6> for i in $(seq 1 8)
do
fadvise file$i 0 999999999 dontneed
done
vmm:/home/akpm> 0 blockdev --setra 4 /dev/hda1
vmm:/mnt/hda6> for i in $(seq 1 8)
do
time cat file$i >/dev/null&
done

cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 13.373 total
cat file$i > /dev/null  0.00s user 0.04s system 0% cpu 14.849 total
cat file$i > /dev/null  0.00s user 0.02s system 0% cpu 15.816 total
cat file$i > /dev/null  0.00s user 0.04s system 0% cpu 16.808 total
cat file$i > /dev/null  0.00s user 0.05s system 0% cpu 17.824 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.004 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.274 total
cat file$i > /dev/null  0.00s user 0.03s system 0% cpu 19.301 total
Quoted 1 line

So with eight files, it's a 300% drop from not using readahead.

yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.

Andrea

#72 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 2 lines · Andrea Arcangeli

what is this fadvise doing?

Invoking fadvise64(). Dropping the pagecache.

Quoted 2 lines

yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.

124k. (Or is it 128k now?)

#73 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 10 lines · Andrew Morton
Quoted 2 lines · Andrea Arcangeli

what is this fadvise doing?

Invoking fadvise64(). Dropping the pagecache.

Quoted 2 lines

yes, and anticipatory scheduler isn't going to fix it. furthmore with IDE the max merging is 64k so you can see little of the whole picture.

124k. (Or is it 128k now?)

sure, sorry, the ide limit is 128k

Andrea

#74 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 15 lines · Andrea Arcangeli
Quoted 4 lines · Andrew Morton
Quoted 2 lines · Hans Reiser

readahead seems to be less effective for non-sequential objects. Or at least, you don't get the order of magnitude benefit from doing only one seek, you only get the better elevator scheduling from having more things in the elevator, which isn't such a big gain.

Quoted 8 lines
Quoted 3 lines

For the spectators of the thread, one of the things most of us learn from experience about readahead is that there has to be something else trying to interject seeks into your workload for readahead to make a big difference, otherwise a modern disk drive (meaning, not 30 or so years old) is going to optimize it for you anyway using its track cache.

The biggest place where readahead helps is when there are several files being read at the same time. Without readahead the disk will seek from one file to the next after having performed a 4k I/O. With readahead, after performing a (say) 128k I/O. It really can make a 32x difference.

Quoted 4 lines

definitely, but again the most important by far is to submit big commands, if you get the 512k commands interleaved by different task it isn't a panic situation.

Well the most important by far is to minimise seeks - you may be able to achieve that by submitting big commands, but you can also do it by accounting by time (not number of requests) and anticipating reads. I'm not saying your way doesn't work.

Quoted 11 lines
Quoted 5 lines

Readahead is brute force. The anticipatory scheduler solves this in a smarter way.

If you decrease readahead with anticipatory scheduler you will submit the small commands, if you decrease the readahead you can stall 10 minutes any write in the queue, and still you won't grow the command in the head of the queue.

Not sure exactly what you mean here, however no big starvation occurs with the scheduler you will find in 2.5.59-mm10 + experimental.

A streaming reader and streaming writer total 14MB/s in agregate throughput, with 2.23 bytes read per write with default settings.

This goes to 11.4MB/s and a ratio of 1.6 with 0 readahead.

When I turn off anticipatory scheduling however, I get a good 17MB/s throughput with a ratio of 0.00 reads per write (actually some small positive epsilon less than one over one hundred).

[snipped]

Quoted 6 lines
Quoted 3 lines

So with eight files, it's a 300% drop from not using readahead.

yes, and anticipatory scheduler isn't going to fix it. furthmore with

I am guessing it will do a pretty good job.

Quoted 3 lines

IDE the max merging is 64k so you can see little of the whole picture.

The disk can't but the io scheduler obviously can. We can give the disk a lot of help.

Quoted 7 lines

Andrea

#75 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 13 lines · Andrew Morton
Quoted 6 lines · Andrea Arcangeli

BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Yes. But ext3 is still doing directory readahead, and I have never noticed it gaining any particular benefit over ext2 from it.

Quoted 10 lines

And neither fs performs inode table readahead.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

reiser4 does directory readahead. It gets a lot of gain from it.

Signature · 1 line
Hans
#76 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 2 lines · Hans Reiser

reiser4 does directory readahead. It gets a lot of gain from it.

What is "a lot"?

#77 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 12 lines · Andrew Morton
Quoted 3 lines · Hans Reiser

reiser4 does directory readahead. It gets a lot of gain from it.

What is "a lot"?

I'll need a bit of time to answer your question. I must confess that I am speaking based on vague memories.

Signature · 1 line
Hans
#78 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrew Morton
Quoted 12 lines · Andrew Morton
Quoted 3 lines · Hans Reiser

reiser4 does directory readahead. It gets a lot of gain from it.

What is "a lot"?

Vladimir Saveliev had the numbers ready at hand after all, and said:

The most noticeable gain is found in the folowing test (not sure that it can be considered as effective readahead though): ls -l over directory containing 30000 files (named numerically) created in random order :
4.87 with no readahead
2.99 with readahead (which is limited by 25% of ram or by directory and all its stat data)

Signature · 1 line
Hans
#79 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 7 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli

On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%

With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).

Anyway that is the theory. It remains to be seen if we can make it work.

Quoted 23 lines
Quoted 9 lines
Quoted 7 lines
Quoted 2 lines

the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.

You seem to be forgetting things like seek time.

I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Andrea

#80 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 25 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 5 lines · Nick Piggin
Quoted 2 lines · Andrea Arcangeli

On Mon, Feb 10, 2003 at 03:58:26PM +1100, Nick Piggin wrote:

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%

Quoted 4 lines

With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).

the way things works, if you give 8k readahead, you'll end submitting 8k requests no matter how long you wait and it will kill throughput to 10% of what was possible to achieve, very especially with scsi, max coalescing of ide is 64k and btw that is its main weakness IMHO.

It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.

Quoted 28 lines

Anyway that is the theory. It remains to be seen if we can make it work.

Quoted 23 lines
Quoted 9 lines
Quoted 7 lines
Quoted 2 lines

the main purpose of readahead is to generate 512k scsi commands when you read a file with a 4k user buffer, anticipatory scheduling isn't very related to readahead.

You seem to be forgetting things like seek time.

I didn't say it's the only purpose. Of course there's no hope for merging in the metadata dependent reads of the fs where anticipatory scheduling does its best, and infact they don't even attempt to do any readhaead. BTW, one thing that should definitely do readhaead and it's not doing that (at least in 2.4) is the readdir path, again to generate big commands, no matter the seeks. It was lost with the directory in pagecache.

Andrea

Andrea

#81 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 37 lines · Andrea Arcangeli
Quoted 29 lines · Nick Piggin
Quoted 14 lines · Andrea Arcangeli
Quoted 11 lines · Nick Piggin
Quoted 7 lines · Andrea Arcangeli
Quoted 4 lines · Nick Piggin

Remember that readahead gets scaled down quickly if it isn't getting hits. It is also likely to be sequential and in the track buffer, so it is a small cost.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

Huge readahead is a problem however anticipatory scheduling will hopefully allow good throughput for multiple read streams without requiring much readahead.

What I mean by this is: if we have >1 sequential readers (eg. ftp server), lets say 30MB/s disk, 4ms avg seek+settle+blah time, submitting reads in say 128KB chunks alternating between streams will cut throughput in half... At 1MB readahead we're at 89% throughput. At 2MB, 94%

Quoted 5 lines

With anticipatory scheduling, we can give each stream say 100ms so thats 96% with, say... 8K readahead if you like. (Yes, I am aware that CPU/PCI/IDE efficiency also mandates a larger request size).

Quoted 9 lines

the way things works, if you give 8k readahead, you'll end submitting 8k requests no matter how long you wait and it will kill throughput to 10% of what was possible to achieve, very especially with scsi, max coalescing of ide is 64k and btw that is its main weakness IMHO.

It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.

I mean you kill throughput by submitting non linear requests. OK with such small requests you probably would lose some throughtput due to much greater ratio of overheads to work done, but in general we are talking about disk head positioning. 10 1MB requests should be much quicker than 1000 10K requests, for disk performance.

#82 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli
Quoted 4 lines · Andrea Arcangeli

On Mon, Feb 10, 2003 at 07:27:51PM +1100, Nick Piggin wrote:
It doesn't make any sense to me your claim that you can decrease the readahead by adding anticipatory scheduling, if you do you'll run so slow at 8k per request in all common workloads.

Readahead kills seeks and command overhead at the expense of maybe transfering data needlessly over the bus and consuming RAM.

AS kills seeks. (At the expense of delaying some IO a tiny bit.)

If unecessary seeks are the main problem, with AS smaller READA is possible. If command overhead is a problem, READA needs to be large.

Regards,

Signature · 3 lines
Kurt Garloff  <[email protected]>                          Eindhoven, NL
GPG key: See mail header, key servers                 SuSE Labs (Head)
SuSE Linux AG, Nuernberg, DE                            SCSI, Security
#83 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 7 lines · Kurt Garloff

Readahead kills seeks and command overhead at the expense of maybe transfering data needlessly over the bus and consuming RAM.

AS kills seeks. (At the expense of delaying some IO a tiny bit.)

If unecessary seeks are the main problem, with AS smaller READA is possible. If command overhead is a problem, READA needs to be large.

Think about reading inode blocks or a bunch of related .h files. We can't nicely do readahead in either of these scenarios, but AS should take care of them nicely...

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#84 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Jakob Oestergaard
Quoted 11 lines · Jakob Oestergaard
Quoted 9 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

Quoted 7 lines
Quoted 2 lines

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

Yes, they are treated the same. If any part of the request is to be waited upon then the whole request should be treated as synchronous.

And if no part of a readahead request is waited upon, we should never have submited it anyway.

Quoted 4 lines

If we assume they are synchronous, that would be rather unfair especially on multi-user systems - and the 90% accuracy that Rik suggested would seem exaggerated to say the least (accuracy would be more like 10% on a good day).

The simplified assumption that "reads are waited upon and writes are not" is highly accurate.

I want to see the Linux I/O scheduler work as well as possible with workloads which make that assumption 100% true. Once we have done that, then we can start worrying about corner cases like AIO, O_SYNC, truncate, etc.

#85 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Jakob Oestergaard
Quoted 10 lines · Jakob Oestergaard
Quoted 9 lines · Andrew Morton
Quoted 4 lines · David Lang

note that issuing a fsync should change all pending writes to 'syncronous' as should writes to any partition mounted with the sync option, or writes to a directory with the S flag set.

We know, at I/O submission time, whether a write is to be waited upon. That's in writeback_control.sync_mode.

Quoted 7 lines
Quoted 2 lines

That, combined with an assumption that "all reads are synchronous" would allow the outgoing BIOs to be appropriately tagged.

This may be a terribly stupid question, if so pls. just tell me :)

I assume read-ahead requests go elsewhere? Or do we assume that someone is waiting for them as well?

readahead is meant for merging. So in short normally there is no additional request generated by readhaead. Inter-process merging must not be forbidden by SFQ.

We also have to choose if to forbid or not outer-process merging. In theory SFQ would tell us to avoid it, and to only merge in the context of the same pid, in the common case it should just take care of most merging, things like dbench aren't going to run well with SFQ no matter if we do global merging or only per-process merging. Optimizing for throughput is not the object here.

Andrea

#86 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Rik van Riel
Quoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

"The only way" ? That sounds like a lack of fantasy ;))

Took about 30 minutes, but here is an alternative algorithm. One that doesn't suffer from SFQ's "temporary unfairness due to unlucky hashing" problem, which can be made worse with SQF's "rehashing once every N seconds" policy, where N is too big for the user, say 30 seconds.

It requires 2 extra fields in the struct files_struct:

	->last_request and
	->request_priority

where ->last_request is the time (jiffies value) when a process associated with this files_struct last submitted an IO request and ->request_priority is a floating average of the time between IO requests, which can be directly used to determine the request priority.

The floating priority is kept over (1 << RQ_PRIO_SHIFT) requests, maybe 32 would be a good value to start ? Maybe 128 ?

The request priority of the files_struct used by the current process can be calculated in a simple O(1) way every time a request is submitted:

{
	struct files_struct *files = current->files;
	unsigned long interval = jiffies - files->last_request;

	files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO);
	files->request_priority += interval;
}

The request_priority gets assigned as the priority of the currently submitted request (or the request gets submitted in the queue belonging to this priority range). We don't change the priority of already submitted requests, except maybe when merging requests.

This idea should adapt faster to changing IO usage of tasks and is O(1) scalable. Dunno if it'll be better than SFQ in practice too, but it just shows that SFQ isn't the only way. ;)

have fun,

Rik

Signature · 3 lines
Bravely reimplemented by the knights who say "NIH".
http://www.surriel.com/		http://guru.conectiva.com/
Current spamtrap:  <a href=mailto:"[email protected]">[email protected]</a>
#87 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 45 lines · Rik van Riel
Quoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

"The only way" ? That sounds like a lack of fantasy ;))

Took about 30 minutes, but here is an alternative algorithm. One that doesn't suffer from SFQ's "temporary unfairness due to unlucky hashing" problem, which can be made worse with SQF's "rehashing once every N seconds" policy, where N is too big for the user, say 30 seconds.

It requires 2 extra fields in the struct files_struct:

	->last_request and
	->request_priority

where ->last_request is the time (jiffies value) when a process associated with this files_struct last submitted an IO request and ->request_priority is a floating average of the time between IO requests, which can be directly used to determine the request priority.

The floating priority is kept over (1 << RQ_PRIO_SHIFT) requests, maybe 32 would be a good value to start ? Maybe 128 ?

The request priority of the files_struct used by the current process can be calculated in a simple O(1) way every time a request is submitted:

{
	struct files_struct *files = current->files;
	unsigned long interval = jiffies - files->last_request;

	files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO);
	files->request_priority += interval;
}

The request_priority gets assigned as the priority of the currently submitted request (or the request gets submitted in the queue belonging to this priority range). We don't change the priority of already submitted requests, except maybe when merging requests.

Quoted 3 lines

This idea should adapt faster to changing IO usage of tasks and is O(1) scalable. Dunno if it'll be better than SFQ in practice too, but it just shows that SFQ isn't the only way. ;)

The file level is worthless IMHO, you have no idea of what is going on in the I/O queue from there, the queue can be filled with 64M in some msec. If you really thing the above can be nearly as good at SFQ at the queue level, implement your alternate solution, benchmark it against SFQ with a seeking tiotest 1 with a cp /dev/zero . in background, if it works better than SFQ we'll use it.

Andrea

#88 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Rik van Riel
Quoted 6 lines · Rik van Riel
Quoted 2 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

"The only way" ? That sounds like a lack of fantasy ;))

you can do more but you'd need to build additional APIs, to allow the highlevel (possibly userspace too) to give hints to the lowlevel.

This only requires the pid and checking current->mm which is trivial. So without adding a complex API I think this is the best/only thing you can do to get close to the minimal possible I/O latency from a process point of view.

Quoted 12 lines

On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.

Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.

Quoted 8 lines

If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.

The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.

I'm not saying anticipatory scheduling is going to be obsoleted by SFQ, especially because SFQ has to be an option to use only when absolutely your only care to get the lowest possible I/O latency from a per-process point of view (like while playing an mpeg or mp3).

But I still definitely think that if you run an anticipatory scheduling benchmark w/ and w/o SFQ, the effect w/o SFQ (i.e. right now) is going to be much more visible than w/ SFQ enabled. The reason is the size of the queue that w/o SFQ can be as large as several seconds in time and several dozen mbytes in bytes.

Andrea

#89 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 47 lines · Andrea Arcangeli
Quoted 8 lines · Rik van Riel
Quoted 3 lines · Andrea Arcangeli

The only way to get the minimal possible latency and maximal fariness is my new stochastic fair queueing idea.

"The only way" ? That sounds like a lack of fantasy ;))

you can do more but you'd need to build additional APIs, to allow the highlevel (possibly userspace too) to give hints to the lowlevel.

This only requires the pid and checking current->mm which is trivial. So without adding a complex API I think this is the best/only thing you can do to get close to the minimal possible I/O latency from a process point of view.

Quoted 12 lines

On the contrary, once we have SFQ to fix the biggest elevator problems the difference made by the anticipatory scheduler should be much more visible.

Think of a disk with 6 track buffers for reading and a system with 10 active reader processes. Without the anticipatory scheduler you'd need to go to the platter for almost every OS read (because each process flushes out the track buffer for the others), while with the anticipatory scheduler you've got a bigger chance of having the data you want in one of the drive's track buffers, meaning that you don't need to go to the platter but can just do a silicon to silicon copy.

Quoted 9 lines

If you look at the academic papers of an anticipatory scheduler, you'll find that it gives as much as a 73% increase in throughput. On real-world tasks, not even on specially contrived benchmarks.

The only aspect of the anticipatory scheduler that is no longer needed with your SFQ idea is the distinction between reads and writes, since your idea already makes the (better, I guess) distinction between synchronous and asynchronous requests.

I'm not saying anticipatory scheduling is going to be obsoleted by SFQ, especially because SFQ has to be an option to use only when absolutely your only care to get the lowest possible I/O latency from a per-process point of view (like while playing an mpeg or mp3).

Quoted 6 lines

But I still definitely think that if you run an anticipatory scheduling benchmark w/ and w/o SFQ, the effect w/o SFQ (i.e. right now) is going to be much more visible than w/ SFQ enabled. The reason is the size of the queue that w/o SFQ can be as large as several seconds in time and several dozen mbytes in bytes.

You are addressing a fundamentally different problem. In the 2.5 elevator we can have whatever queue size we like. I get great contest results with a 8192 request queue size. We track each request submission time so we can impose a soft upper limit on service times which provides fine latency, and the sync nature of reads ensures pretty good fairness.

What your scheduler is good for obviously is providing a much stronger per process fairness solution which is obviously very useful for some tasks.

The problems each are trying to solve are different. I don't think your idea solves anything that anticipatory scheduling solves (tries to).

Nick

#90 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.

In reply to Rik van Riel
Quoted 6 lines

In the time of one disk seek plus half rotational latency (12 ms) you can do a pretty large amount of reading (>400kB). This means that for near and medium disk seeks you don't care all that much about how large the submitted IO is. Track buffers further reduce this importance.

This isn't always true. Removable devices usually have a quite low seek time compared to their raw transfer rate.

Bye.

#91 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli

Hi!

Quoted 6 lines

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and

What about adding speicial queue (queues?) for niced things? That way nice -20 job would not interfere with normal processes, not even for I/O.
Pavel

Signature · 2 lines
Worst form of spam? Adding advertisment signatures ala sourceforge.net.
What goes next? Inserting advertisment *into* email?
#92 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 9 lines · Pavel Machek

Hi!

Quoted 6 lines

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you probably want a perturbation timer that will change the hash function every 30 sec or so. Plus I want a special queue for everything asynchronoys. So that the asynchronoys queue will be elevated and

Quoted 3 lines

What about adding speicial queue (queues?) for niced things? That way nice -20 job would not interfere with normal processes, not even for I/O.

Once you have per-process queues, it's fairly trivial to add stuff like that.

Signature · 1 line
Jens Axboe
#93 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

In reply to Andrea Arcangeli

Hi!

Quoted 4 lines

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you

Well, if you want *fair* scheduler, as in "fair between users", I guess you should base it on task->uid.

That should solve your dbench problems, too, as you are very unlikely to see two tasks working over same data with different uids.

Pavel

Signature · 2 lines
Worst form of spam? Adding advertisment signatures ala sourceforge.net.
What goes next? Inserting advertisment *into* email?
#94 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 9 lines · Pavel Machek

Hi!

Quoted 4 lines

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you

Well, if you want *fair* scheduler, as in "fair between users", I guess you should base it on task->uid.

Good idea. All these cases should be optional, and they make plenty of sense to me.

Quoted 2 lines

That should solve your dbench problems, too, as you are very unlikely to see two tasks working over same data with different uids.

yes, but the main reason we do this isn't for multiuser systems. For multiuser systems it's true it would solve dbench, but there must be an option to go with task->pid and being able to specify the latency criticak tasks from userspace would be a good idea too.

Andrea

#95 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Andrea Arcangeli
Quoted 7 lines · Pavel Machek

Hi!

Quoted 4 lines

The design I proposed is to have multiple I/O queues, where to apply the elevator, and to choose the queue in function of the task->pid that is sumbitting the bh/bio. You'll have to apply an hash to the pid and you

Quoted 5 lines
Quoted 2 lines

Well, if you want *fair* scheduler, as in "fair between users", I guess you should base it on task->uid.

Good idea. All these cases should be optional, and they make plenty of sense to me.

Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.

Lets lego.

Signature · 1 line
Jens Axboe
#96 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 3 lines · [email protected] said:

Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.

Which again reminds us of the network queueing. You all seem to be reinventing alexey's wheel here. The above reminds me of HTB with SFQ leaf nodes.

By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.

Jason

#97 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 8 lines · Jason Lunz
Quoted 3 lines · [email protected] said:

Coolest would to simply stack these schedulers any way you want. Sneak the uid based fairness scheduler in front of the pid based one, and you have per-user with per-process fairness.

Which again reminds us of the network queueing. You all seem to be reinventing alexey's wheel here. The above reminds me of HTB with SFQ leaf nodes.

There's no wheel reinventing here, just applying the goodies from network scheduling to disk scheduling.

Quoted 2 lines

By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.

Well, that's the point.

Signature · 1 line
Jens Axboe
#98 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 4 lines · [email protected] said:
Quoted 2 lines

By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.

Well, that's the point.

Yes, what you've done with cbq is great. What I was referring to, though, is the user configurability of network frame queueing. It's possible to do really complex things for very specialized needs, yet also easy to put in a simple tweak if there's just one type of traffic you need to prioritize. It'd be nice to have that kind of configurability for unusual i/o loads, and the arbitrary queue stacking is a whole different beast than having a couple of tunables to tweak.

Jason

#99 lore raw

Re: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]

Quoted 6 lines · Jason Lunz
Quoted 4 lines · [email protected] said:
Quoted 2 lines

By all means, do the same thing with disk i/o. It's been a smashing success with packet queueing.

Well, that's the point.

Quoted 7 lines

Yes, what you've done with cbq is great. What I was referring to, though, is the user configurability of network frame queueing. It's possible to do really complex things for very specialized needs, yet also easy to put in a simple tweak if there's just one type of traffic you need to prioritize. It'd be nice to have that kind of configurability for unusual i/o loads, and the arbitrary queue stacking is a whole different beast than having a couple of tunables to tweak.

That is indeed the goal. We'll see how much is doable within the 2.6 time frame, though.

Signature · 1 line
Jens Axboe