s1gyn has quit [Remote host closed the connection]
pretty_dumm_guy has quit [Quit: WeeChat 3.5]
gog has quit [Read error: Connection reset by peer]
gildasio has quit [Ping timeout: 268 seconds]
gildasio has joined #osdev
gog has joined #osdev
gildasio has quit [Remote host closed the connection]
gildasio has joined #osdev
[itchyjunk] has quit [Ping timeout: 244 seconds]
frkazoid333 has quit [Read error: Connection reset by peer]
SGautam has quit [Quit: Connection closed for inactivity]
[itchyjunk] has joined #osdev
gildasio has quit [Ping timeout: 268 seconds]
gildasio has joined #osdev
gog has quit [Quit: byee]
gog has joined #osdev
gildasio has quit [Remote host closed the connection]
gildasio has joined #osdev
gildasio has quit [Client Quit]
octo has joined #osdev
<octo>
Hi, osdev newbie here. I'm playing around with writing a keyboard driver in protected mode. My code simply maintains an array `volatile bool keystates[256]`, where the keyboard interrupt handler sets/unsets the bool at the index of the scancode when a key is pressed/released. It works fine when I check keystates by doing something like `if
<octo>
(keystates[SCANCODE_W]) {}`. I tried to abstract this by wrapping it in a `is_key_down(int scode) {return keystates[scode];}` function, but now if I call is_key_down repeatedly very fast (i.e. in a tight loop), total chaos ensues and i eventually get a triple fault. Why does this behavior happen?
<heat>
because something else is screwed
<heat>
I'm guessing stack
<heat>
check your interrupt handlers
<octo>
Should they be doing something other than an `outb 0x20, 0x20` and `iret`?
<heat>
probably?
X-Scale` has joined #osdev
<heat>
depends on the rest of the interrupt handler
<heat>
do you have a link, snippet, anything?
<octo>
The keyboard ISR is justL `call c_kbd_int_handler`, `mov 0x20, 0x20`, `iret`
X-Scale has quit [Ping timeout: 276 seconds]
X-Scale` is now known as X-Scale
<heat>
there you go
<heat>
context corruption
<heat>
imagine: c_kbd_int_handler uses eax, you then EOI (out 0x20, 0x20), and iret
<octo>
Guess I need to do more reading? :-)
<heat>
what happens to eax?
<heat>
cmon this is an easy question
xenos1984 has quit [Read error: Connection reset by peer]
<heat>
you're overthinking it
<octo>
ohh I need to pushad
<octo>
lol
<heat>
and popad
<octo>
:)
<octo>
thanks
<heat>
although AFAIK usually pushad and popad aren't used because they push superfluous stuff
<heat>
and they're not there in 64-bit mode
<heat>
so you push it all manually
<heat>
octo, np
zaquest has quit [Remote host closed the connection]
zaquest has joined #osdev
X-Scale has quit [Ping timeout: 272 seconds]
heat has quit [Ping timeout: 272 seconds]
octo has quit [Quit: Connection closed]
gog has quit [Ping timeout: 240 seconds]
[itchyjunk] has quit [Remote host closed the connection]
xenos1984 has joined #osdev
gog has joined #osdev
frkzoid has joined #osdev
curi0 has joined #osdev
skipwich has quit [Quit: DISCONNECT]
skipwich has joined #osdev
dude12312414 has quit [Quit: THE RAM IS TOO DAMN HIGH]
X-Scale has joined #osdev
curi0 has quit [Remote host closed the connection]
smeso has quit [Quit: smeso]
smeso has joined #osdev
frkzoid has quit [Read error: Connection reset by peer]
<doug16k>
octo's isr needs hope that they didn't change ds too
<doug16k>
ah it's 64 bit, doesn't in that case
<doug16k>
xor %eax,%eax ; mov %ax,%ds ; int3 kills most people's i386 kernel from what I've seen
<doug16k>
they think ds works
<doug16k>
ss being valid makes it seems like they can access memory
<doug16k>
likely to just recurse into page fault endlessly when it touches something, and everything is annihilated by the time it stops
opal has quit [Ping timeout: 268 seconds]
<doug16k>
sorry recurse into GP
<doug16k>
it would be comical to handle GP to load segments and ignore them in the context switch
<doug16k>
would be ridiculous because other threads can see you changing ds if they don't use it and just read ds
doug16k has quit [Quit: Leaving]
curi0 has joined #osdev
<curi0>
So if anyone wants update on what happened to trying to move and resize BAR I got it to work and booting OS (both Linux and Windows) both show the new BAR size. Only problem is that EFI graphics stop working when I move BAR so I don't get video until OS boots
<curi0>
and the fact that everything in it hardcoded lol
opal has joined #osdev
curi0 has quit [Read error: Connection reset by peer]
vai has joined #osdev
<vai>
toilet suffered me having the core dump
zid has quit [Read error: Connection reset by peer]
<vai>
Do you actually have the feature in the kernel/OS? Core dump? Wow. Thats rare for a beginner.
theruran has quit [Quit: Connection closed for inactivity]
curi0 has joined #osdev
<geist>
ah there we go. found the last remaining bug (that i know of) int eh 6800 emulator
<geist>
bad flags calculation when subtracting accumulator B from A
<curi0>
any idea why i see rainbows on the windows boot screen after moving BAR and resizing it ? the new location should be empty and not have anything to show rainbows. it works perfectly without any issues after the gpu driver loads though
<curi0>
i think i might have to clear the memory or something ?
<curi0>
it doesnt happen with moving alone. only moving it and resizing to 8gb
<curi0>
there are no overlaps/conflicts since im using exactly what linux gives to it
<geist>
how are you resizing it?
vai has quit [Remote host closed the connection]
<curi0>
geist, resizable bar capability
Dyyskos has joined #osdev
<curi0>
after moving it and the bridge window
onering has joined #osdev
nanovad_ has joined #osdev
Dyskos has quit [Read error: Connection reset by peer]
teroshan has quit [Quit: Ping timeout (120 seconds)]
ckie has quit [Quit: off I go~]
nanovad has quit [Quit: ZNC 1.7.5+deb4 - https://znc.in]
ngc0202 has quit [Quit: Signed off]
zhiayang has quit [Quit: oof.]
PapaFrog has quit [Quit: ZNC 1.8.2+deb2 - https://znc.in]
Beato has quit [Quit: I have been discovered!]
nanovad_ is now known as nanovad
mzxtuelkl has joined #osdev
wolfshappen_ has quit [Read error: Connection reset by peer]
LostFrog has joined #osdev
zhiayang_ has joined #osdev
ckie has joined #osdev
wolfshappen has joined #osdev
zhiayang_ is now known as zhiayang
JTL has quit [Ping timeout: 264 seconds]
sprock has quit [Ping timeout: 268 seconds]
cross has quit [Ping timeout: 268 seconds]
ngc0202 has joined #osdev
sprock has joined #osdev
cross has joined #osdev
the_lanetly_052_ has joined #osdev
JTL has joined #osdev
curi0 has quit [Remote host closed the connection]
jack_rabbit has quit [Ping timeout: 244 seconds]
curi0 has joined #osdev
knusbaum has joined #osdev
curi0 has quit [Quit: Leaving]
jack_rabbit has joined #osdev
knusbaum has quit [Ping timeout: 260 seconds]
the_lanetly_052 has joined #osdev
the_lanetly_052_ has quit [Ping timeout: 272 seconds]
the_lanetly_052_ has joined #osdev
eroux has quit [Read error: Connection reset by peer]
the_lanetly_052 has quit [Ping timeout: 260 seconds]
eroux has joined #osdev
<geist>
ah resizable bar capability. makes sense. i was wondering what the mechanism was to actually change the size of the bar
foudfou has quit [Remote host closed the connection]
foudfou has joined #osdev
GeDaMo has joined #osdev
pretty_dumm_guy has joined #osdev
the_lanetly_052 has joined #osdev
the_lanetly_052_ has quit [Ping timeout: 240 seconds]
MarchHare has joined #osdev
scaleww has joined #osdev
wand has quit [Remote host closed the connection]
wand has joined #osdev
wand has quit [Remote host closed the connection]
wand has joined #osdev
MarchHare has quit [Ping timeout: 268 seconds]
X-Scale` has joined #osdev
zid has joined #osdev
X-Scale has quit [Ping timeout: 244 seconds]
X-Scale` is now known as X-Scale
toaaster has joined #osdev
the_lanetly_052 has quit [Remote host closed the connection]
toaaster has quit [Quit: leaving]
heat has joined #osdev
X-Scale` has joined #osdev
X-Scale has quit [Ping timeout: 240 seconds]
X-Scale` is now known as X-Scale
the_lanetly_052 has joined #osdev
foudfou has quit [Remote host closed the connection]
foudfou has joined #osdev
sortie has quit [Quit: Leaving]
sortie has joined #osdev
elastic_dog has quit [Ping timeout: 260 seconds]
elastic_dog has joined #osdev
tsraoien has joined #osdev
gildasio has joined #osdev
gog has quit [Ping timeout: 240 seconds]
tsraoien has quit [Ping timeout: 268 seconds]
gildasio has quit [Ping timeout: 268 seconds]
gildasio has joined #osdev
the_lanetly_052 has quit [Ping timeout: 268 seconds]
gildasio has quit [Remote host closed the connection]
gildasio has joined #osdev
elastic_dog has quit [Ping timeout: 240 seconds]
nj0rd has quit [Quit: WeeChat 3.5]
nj0rd has joined #osdev
elastic_dog has joined #osdev
<zid>
27.6C, I blame heat
<friedy>
zid: that's cold
<zid>
I think you'll find it is infact, near the upper limit of what humans can survive
<friedy>
zid: I meant blaming heat is pretty cold.
<zid>
Nope it's completely normal, he is the instigator of all our ills
<bslsk05>
randomascii.wordpress.com: Slower Memory Zeroing Through Parallelism | Random ASCII – tech blog of Bruce Dawson
<mjg_>
wait
<mjg_>
windows is zeroing memory on *free*?
<mjg_>
i mean munmap in unix parlance
<mjg_>
> Now I’m not a kernel developer but I’m pretty sure if you’re spending most of your time in a function with WaitForSpinLock in its name then something bad has happened. As somebody wise once said, spin locks waste energy and CPU power and should be avoided.
<mjg_>
this bullshit again
<mjg_>
maybe i'll respond to the post
<mrvn>
and that's why I have per core memory.
<mrvn>
mjg_: The spinning part of a spin lock should be avoided
* FireFly
spins
octo has joined #osdev
<octo>
How can I get ld to relocate the .bss section to a certain address, but not actually include the section in the outputted flat binary?
<\Test_User>
strip -R .bss, after you figured out how to put it at a specific address?
<octo>
I'm not dumping it though, im using ld's "binary" target so ld makes the binary itself
<mrvn>
Note that all your noload sections must be at the end.
<zid>
cannot recommend
<zid>
intermediate elf means you can do fun things
<mrvn>
\Test_User: that just fights a symptom and doesn't fix the bug in the linker script
<\Test_User>
fair enough
<mrvn>
octo: what does readelf say for the flags on the .bss section?
<octo>
._.
<octo>
its a flat binary not an elf
<zid>
cannot recommend
<zid>
intermediate elf means you can do fun things
<octo>
Ok, I will change my Makefile to use an intermediate elf then :-)
<octo>
thanks
<mrvn>
Your linking from object files directly to flat binary?
<mrvn>
How do you use gdb on that? Create a system.map? objdump to check some function compiled right? ....
<octo>
I just objdump on the object files?
<zid>
objcopy
<zid>
objdump is the disassembler mainly
<zid>
-j .section -o blah.bin
<mrvn>
octo: objdump on the objects won't have all the address fixups the final linking does. Sometimes you need those.
<octo>
mrvn: true, but I'm just playing around atm, haven't gotten that advanced yet
<mrvn>
or if you are doing -fLTO then the objects are quite meaningless
<mrvn>
anyway, most of use do source -> object -> elf -> binary
<octo>
is there a flag to get ld to print out availible targets?
<sortie>
I'm curious, what are you using a binary for?
<sortie>
*a flat binary for?
<octo>
bootloader
<sortie>
A statically linked ELF binary is really simple to load. If you got a second stage or enough space in the first space, you could consider using ELF and avoiding all the trickeries of C -> flat binaries, which can be difficult to do right (because the format is too simple), and then you got all the power of the ELF tools
<sortie>
Depends on your constraints for the bootloader of course :)
<octo>
Yes, that is definitely one of the next steps for my project
nilum has joined #osdev
<octo>
Woah, that bss was really bloating up the binary size hehe
<octo>
- 2K
<mrvn>
sortie: I would still do ELF -> binary. best of both worlds.
<octo>
I am doing elt -> binary now :-)
<octo>
elf*
<sortie>
mrvn, well you can't e.g. objdump such flat binaries (at least without trickery)
<mrvn>
hence the ELF intgermediate
<sortie>
Yeah if you keep it around for e.g. debugging
<octo>
ld preserves the order of sections in the SECTIONS{} block, right? Like if I declare my .bss after the .text, it will be at a higher address?
<mrvn>
obviously. Make everything .PRECIOUS. Deleting intermediate files is a horrible practice from when source was larger than your porn collection
<mrvn>
octo: if you don't alter . then it increments contiguously.
<mrvn>
octo: which has nothing to do with location in the file though
<octo>
but when objcopying it to a binary, it gets put in the actual location?
<zid>
it's not preserving or not preserving anything, you're telling it what the order is
<zid>
the bit between the {} is the contents of the output elf
<zid>
you're basically just writing an elf out in words
<mrvn>
octo: yes, including any padding needed
<mrvn>
zid: the order in the file is a bit random and only loosely based on the linker script
<zid>
i.e you could write { .banana : { LONG(7); } } for an ELF that's contains a section called .banana with a single int of 7 in it .. if you wanted
<zid>
*usually* what you do though is smack things from your input files in instead
gog has quit [Ping timeout: 272 seconds]
octo has quit [Quit: Connection closed]
theruran has joined #osdev
friedy has left #osdev [#osdev]
friedy has joined #osdev
mzxtuelkl has quit [Quit: Leaving]
gog has joined #osdev
nilum has quit [Remote host closed the connection]
bauen1 has quit [Ping timeout: 244 seconds]
frkzoid has joined #osdev
mrvn has quit [Ping timeout: 256 seconds]
terminalpusher has joined #osdev
jafarlihi has joined #osdev
teroshan has joined #osdev
teroshan has quit [Client Quit]
<jafarlihi>
Does anyone here know anything about netlink?
teroshan has joined #osdev
jafarlihi has quit [Ping timeout: 272 seconds]
blockhead has joined #osdev
nilum has joined #osdev
Vercas has joined #osdev
nilum has quit [Remote host closed the connection]
Terlisimo has quit [Quit: Connection reset by beer]
MarchHare has joined #osdev
mrvn has joined #osdev
<gog>
isn't there a channel for Linux kernel hacking
<GeDaMo>
##kernel 111 :Linux kernel discussion
<GeDaMo>
Also #kernel 71 :Channel for linux, unix-like kernel discussion
<GeDaMo>
And also some distro-specific kernel channels
<zid>
oftc is where all the linux shit is afaik
Terlisimo has joined #osdev
<mrvn>
"Given an integer array "nums" where every element appears three times except fro one, which appears exactly once. Find the single element and return it in linear time and constant space." Is that even possible?
[itchyjunk] has quit [Remote host closed the connection]
[itchyjunk] has joined #osdev
<mrvn>
It's easy to do in O(n log n) time or with O(n) space. But as stated?
<GeDaMo>
Any information on how many numbers or their range?
<mrvn>
Sure. But that is irrelevant for O() notation
<mrvn>
range is "int" by the way
<mrvn>
So obviously the length must be <= 3 * UINT_MAX
<gog>
does each element appear in sequence?
<gog>
so like 1 1 1 2 3 3 3 ...
<mrvn>
Lets make an array<uint8_t, UINT_MAX> count;, count all the elements and then check the array for the one with count 1. That's O(n) since the array is constant size, right? :)
<mrvn>
gog: no.
<gog>
hm
<mrvn>
Example: [0,1,0,1,0,1,99]
<gog>
oh that's less trivial then
<mrvn>
If it where only "two times" you could XOR all the elements together.
<GeDaMo>
You can eliminate number when you encounter it more than once
<gog>
yes
<mrvn>
GeDaMo: [1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8] How does that help?
<GeDaMo>
Does this involve summing?
<mrvn>
GeDaMo: how would that help?
<GeDaMo>
I don't know, I'm thinking out loud
<dh`>
it's possible if you assume "integer" in "integer array" means "machine integer"
<moon-child>
hmmm maybe something similar to xor though
<moon-child>
track two accumulated values, with two appropriately-chosen operations
<moon-child>
maybe
<dh`>
I think
<mrvn>
dh`: 20:56 < mrvn> Lets make an array<uint8_t, UINT_MAX> count;... That's not how O() notation is supposed to be used
<GeDaMo>
If the range of the numbers is consecutive e.g. 1..9, you can calulate the sum and subtract values
<mrvn>
GeDaMo: but they aren't :(
<GeDaMo>
You didn't say that :|
<dh`>
imagine that your constant space is unsigned x[(1 << CHAR_BIT) * sizeof(int)]
<mrvn>
dh`: cheater
<dh`>
how is that cheating?
<mrvn>
"That's not how O() notation is supposed to be used"
<moon-child>
waitaminnit, how do you do it in nlogn time?
<dh`>
huh?
<GeDaMo>
I thought about a bit set but there being 3 copies of each value makes it difficult
<dh`>
moon-child: sort and scan
<moon-child>
I assumed sorting or similar, but that also involes n space
<mrvn>
moon-child: sort the array and then linear search
<moon-child>
oh
<dh`>
mrvn, everything in what I wrote is O(1)
<moon-child>
I assumed based on 'O(n log n) time or with O(n) space' that the nlogn time solution had better than n space
<mrvn>
moon-child: you sort in-place.
<moon-child>
oh, I was assuming you couldn't stomp on the input
<mrvn>
Doesn't say I can't so I assume I can.
<moon-child>
in that case I think it's probably doable
<moon-child>
with something like a hash table
<mrvn>
hash table is O(n log n) too since you need log n re-hashes
<moon-child>
why?
<dh`>
if you want to consider the machine word size a scaling parameter then you definitely can't do it because everything's exponential
<mrvn>
or even n
<mrvn>
moon-child: you have to build the hash table in "nums" so you have to start with size 1, then 2, 3, 4, 5,
<mrvn>
dh`: lets say the machine word size is infinite.
<moon-child>
mrvn: I was imagining some scheme where you do it completely in-place
<mrvn>
moon-child: me too, that's why you have to re-hash
<moon-child>
start with the first number, hash it, use that to find a target index
<dh`>
mrvn, that's meaningless
<moon-child>
in the whole array
<moon-child>
then look up whatever used to be in the target index next
<moon-child>
never rehashing
<mrvn>
moon-child: How do you know if an entry is hashed or original?
<moon-child>
that's the tricky part!
<moon-child>
can reserve up to a constant number of sentinel values
<moon-child>
tracking info on those values outside the array, if you encounter them
<moon-child>
but I'm not sure if that's enough
<dh`>
but if you mean an array of bignums, then it's also possible using a different set of tricks
<mrvn>
moon-child: if the numbers are bad you run out of sentinels
<moon-child>
if the numbers are bad then your hash table is n^2 anyway
<mrvn>
moon-child: Also how do you count in the hashtable? You need 2 ints for that. So every number you have you have to save 2.
<mrvn>
dh`: what trick that doesn't involve cheating on the constant space by using some maximum space?
<moon-child>
mrvn: fortunately, for every signifcant value in the array, there are two duplicates
<dh`>
neither of the tricks I've proposed cheat on the constant space
<dh`>
if you have machine integers, you can use the same magic that allows radix sort to sort in linear time
<dh`>
if you have bignums, you can encode the entire array in a single bignum and then do arithmetic on it to figure out the answer
<mrvn>
dh`: "unsigned x[(1 << CHAR_BIT) * sizeof(int)]" uses tha maximum space you might need
<GeDaMo>
That's not a cheat for constant space
<mrvn>
dh`: if I re-ask the same question with uint64_t as inputs your code fails.
<dh`>
no, it doesn't, you just need sizeof(uint64_t)
<mrvn>
dh`: which fails
<dh`>
how?
<mrvn>
It fails to load or malloc returns NULL
<dh`>
because it's linear in the bitsize?
<dh`>
how does 256 * 8 fail malloc even on an 8-bit machine?
<moon-child>
if we're using numbers with a finite number of bits, then of course everything is 'constant time' and 'constant space'. It's just not an interesting way to think about the problem at all
<GeDaMo>
Pfft! Big O has nothing to do with real hardware :P
<mrvn>
dh`: oh, wait. I totaly misread that.
<mrvn>
dh`: Ok, how do you solve this with "unsigned x[(1 << CHAR_BIT) * sizeof(int)]"?
<moon-child>
me too
<FireFly>
(serial experiments lain voice) constant space, constant time *laughter*
<dh`>
mrvn: there are 256 possible byte values, count those
<dh`>
(separately for each byte in the int)
<dh`>
then pick the bytes that appear an extra time
<moon-child>
then it's time-linear for the number of bytes in an int
<mrvn>
dh`: I would consider that O(n log n) because th number of bytes is log n.
<dh`>
what n?
<moon-child>
n log m, surely? Probably the maximum value is not correlated with the number of values
<dh`>
the number of bytes in an int is only reasonably considered fixed
<moon-child>
mrvn | dh`: lets say the machine word size is infinite
<dh`>
as I said before if you want to make the machine word size an input parameter, then everything's exponential and it all ceases to be interesting
<mrvn>
dh`: ok, O(n log m) where m is the domain size and n < m
<mrvn>
dh`: assume a machine with infinite word size that can do simple operations in O(1) on them.
<mrvn>
sizeof(word) == 1 per definition.
<dh`>
n log m? first of all, that's wrong; second of all, it doesn't make sense as a premise
<dh`>
<dh`> if you have bignums, you can encode the entire array in a single bignum and then do arithmetic on it to figure out the answer
<mrvn>
dh`: how?
<mrvn>
dh`: Lets make it more realistic: The machine has a word size big enough for 'n'. So you don't encode each element as some digit in some humongous base.
<dh`>
...so you're going to add completely artificial constraints because you don't like my answer
<mrvn>
And inputs are 0 <= x <= n
<mrvn>
dh`: your answer makes no sense when talking about O() notation. It would make pretty much every problem constant time.
<mrvn>
and space
<dh`>
my answer for uint64_t? no, it doesn't
<mrvn>
dh`: if you answer depends on the size of the operand then you have a "log n" factor in there.
<mrvn>
That's how everyone else uses O() notations
<dh`>
again, first of all, that's wrong; second, it doesn't make sense as a premise
<mrvn>
dh`: Take for example bucket sort. Your way would make sorting linear time.
<dh`>
see "radix sort"
<mrvn>
dh`: same thing
<dh`>
it is linear time
<dh`>
deal
<mrvn>
The number of passes depend on the size of the operand. You are hiding an "log n" factor.
<mrvn>
dh`: it's not arbitrary. It's how everyone else computes O() notation.
<heat>
at least if you keep yourself to the most basic feature set
<moon-child>
it's also an actually somewhat sensible cost model in a parallel context (though granted, in a parallel context you can do the associative reduction in logn ... still)
<ebrasca>
heat: Thank you!
<heat>
ebrasca, np
<heat>
you can ask around here for e1000(e) help, it's a very common NIC to have a driver for
<dh`>
mrvn, no, adding extra things as size parameters is definitely arbitrary
<mrvn>
dh`: I didn't add anything. You defined your extra space dependent on the size of the input.
<dh`>
no, I defined a constant amount of space based on a constant-sized data type
<dh`>
you then decided you wanted to move to a different setting
<mrvn>
dh`: and that is not how everyone else computes O() notation.
<dh`>
it has nothing to do with O() notation, it's about which things are constant
xenos1984 has quit [Read error: Connection reset by peer]
<mrvn>
dh`: O() notation works on a theoretical computing model that has no constant-sized data type. Looking for "lim n->infty" makes no sense with a constant-sized data type for n.
<dh`>
no, O() notation applies to whatever model of computation you decide you're working with
<dh`>
if we decide we're working with unary notation, your solution stops working
<dh`>
but that is also a silly/arbitrary thing to do
<mrvn>
dh`: works fine if you have a machine that can work with unary numbers in constant time.
<mrvn>
kind of hard to do binary operations though.
<dh`>
well yes, it also works fine if you have a machine that can scan an array in constant time
<dh`>
which is equally meaningful
<mrvn>
dh`: The problem with your model is that you limit "n" so your solution is simply O(1).
<dh`>
well yes, sure, by that same logic every real program is O(1) in space
<dh`>
regardless of what it's trying to do or how space-wasteful it actually is
<dh`>
that's not a helpful position to take
<mrvn>
dh`: yes, all but those that might not halt.
<mrvn>
dh`: exactly. Which is why nobody uses your model.
<dh`>
oh, but since the amount of space is bounded you can rule out those that don't halt
<dh`>
no, nobody uses *your* model where machine integers are variable-sized
<dh`>
it is halfway between a meaningful machine-informed model and an abstract model that uses math ints
<dh`>
if there's an issue, it's that the initial problem formulation is flawed because it bounds the input
<mrvn>
dh`: we have to agree to disagree. Your model makes everything O(1), my model gives the generally agreed upon answers for standard algorithms.
<dh`>
your model adds extra random factors all over the place
<mrvn>
dh`: my initial question didn't bound anything.
<dh`>
only if you have arbitrarily large integers
<heat>
has there ever been a machine with native word width smaller than the size of an address?
<dh`>
heat: all 8-bits?
<mrvn>
heat: heaps. All 8 bit cpus, AVR
<heat>
hm ok
<dh`>
286 protected mode
<dh`>
8088, for that matter
<mrvn>
heat: x86 PAE?
<heat>
no, not PAE
<mrvn>
32bit words, 36bit physical address
<dh`>
mrvn, you can fix the problem by changing "three times" to "a multiple of three times"
<dh`>
then the array is no longer bounded
<mrvn>
dh`: my array was never bound in the first place.
<dh`>
the entire argument you're making against my approach is that the array is bounded by the machine word size
<heat>
mrvn, physical doesn't matter here
<dh`>
because there's only finitely many distinct machine integers
<mrvn>
dh`: no. my argument is that you bind the algorithm to the word size
<dh`>
so? that's true of nearly anything that runs on a real computer
<dh`>
and the word size isn't a function of the input, it's a fixed property of your turing machine
<mrvn>
dh`: yes. But O() notation is a theoretical thing.
<dh`>
yes, and in a theoretical thing you don't have arrays, but besides that, in a theoretical thing you have math ints, which are themselves unbounded, and you can encode the whole array in one
<dh`>
but you didn't like that answer either
<mrvn>
dh`: you can. Can you solve the problem with that?
<dh`>
sure
dude12312414 has quit [Ping timeout: 268 seconds]
dude12312414 has joined #osdev
<mrvn>
dh`: you still can't encode your "(1 << CHAR_BITS) * sizeof(int)" with that, not without needing "log n" operations to do the encoding.
<dh`>
WLOG assume the integers are nonnegative; scan the array to find the largest, call that K - 1. then scan the array counting how many of each integer there are by multiplying by 4K and adding
<mrvn>
at least I don't see a way to do that
<dh`>
modulo 3
<dh`>
basically you treat your accumulator as a number written in base 4K and count in each digit
JTL1 is now known as JTL
<dh`>
then at the end go through it and find the one with count 1
<dh`>
completely different approach
<dh`>
but it is fine if you have math ints
xenos1984 has joined #osdev
<mrvn>
dh`: "go through it"? Loop over it K times checking t % 4K and t /= 4k?
<dh`>
no, loop over it once
ZipCPU has quit [Ping timeout: 240 seconds]
<dh`>
and actually you don't need to do that, you just need to take the log base 4K to find the nonzero entry
ZipCPU has joined #osdev
opal has quit [Ping timeout: 268 seconds]
opal has joined #osdev
<mrvn>
dh`: Looping would work. Don't see how log would help at all.
ZipCPU_ has joined #osdev
<mrvn>
dh`: write it out using uint64_t as accumulator and numbers small enough not to overflow. It's an interesting approach abut you aren't there yet.
ZipCPU has quit [Ping timeout: 244 seconds]
ZipCPU_ is now known as ZipCPU
noeontheend has quit [Ping timeout: 272 seconds]
<dh`>
aren't I? you'll agree that it works for an array of 2-bit integers of size K rather than a single bignum, right?
<dh`>
(modulo the space that takes)
<mrvn>
dh`: no. the "multiplying by 4K" doesn't work.
<dh`>
right, that's complete crap, sorry
<mrvn>
I think you mend adding 1 << (2 * i)
<dh`>
it's 4K^i
<dh`>
er, (4K)^i
<dh`>
and 3 is enough
<mrvn>
Well that is a problem. pow() isn't O(1) generally.
<dh`>
on math ints it is, it's just another operation
<dh`>
and when it comes down to it, encoding the array in a single bignum is cheating, and the question is ultimately whether it's a cheat you're going to allow or not, and that's arbitrary and depends on whoever's making the rules
<moon-child>
but also, shift is usually considered to be O(1), and you should be able to use shifts here. However I think if you have bignums, then you've already given up entirely on the idea of even measuring space usage
<dh`>
the argument I was making before is that you should either be using math ints or machine ints
<dh`>
(or explicitly modeled bignums)
<mrvn>
dh`: yes. generally you works with data types large enough to hold "n" and not arbitrarily large.
<dh`>
but taking some of the properties of math ints and some of the properties of machine ints is ... fictitious
<mrvn>
The thing is though that the word you use changes with n
<dh`>
that, however, is fictitious
<mrvn>
but it's how everybody else measures it
<dh`>
not that I've seen
<mrvn>
dh`: How long does sorting an array of size N with unique numbers take?
<dh`>
normally you either use math integers and ignore the representation, or use machine integers and take the asymptotic bound ignoring whether there's enough address space to actually handle it
<dh`>
because those are the approaches that produce interesting answers
terminalpusher has quit [Remote host closed the connection]
<dh`>
(the former being theoretically sound and the latter being reasonably useful until you run out of memory)
terminalpusher has joined #osdev
<dh`>
mrvn, it takes at least O(N log N) for any comparison-based sort and O(N) for radix sort
<dh`>
radix sort is not subject to the sorting theorem because it's a hash, not a sort.
<mrvn>
dh`: except in the later you don't allow certain construct that depend on the machine word size without counting it. Like radix sort having that "w" factor in there for the key length.
<dh`>
sure you do. because that w is a constant
<dh`>
(unless you start sorting strings, that's when it gets interesting)
<mrvn>
that w is the log n factor from sorting.
<dh`>
no, it definitely is not.
vdamewood has quit [Quit: My MacBook Pro has gone to sleep. ZZZzzz…]
<moon-child>
yes, it's the log of something completey different
<mrvn>
at least if your input numbers and number count use the same type
<moon-child>
:P
<mrvn>
dh`: point is that you have that "w" factor in there. Your original code has such a "w" factor too with the sizeof(int).
<dh`>
put it this way: if I have arrays of 1000 and 10000 8-bit bytes, sorting them with radix sort takes 1 and 10 time units respectively
<dh`>
sorting them with quicksort takes 1 and something like 15 (different) time units
<mrvn>
dh`: you mean 8000 and 80000 units
<dh`>
no, not 15, maybe 12
<dh`>
the fact that an array of 10000 8-bit bytes must have a lot of duplicate values is completely immaterial
<mrvn>
and quicksor can be 100000000 units
<dh`>
you're missing the point
<dh`>
radix sort is linear in the input length, so a 10x array takes 10x longer
jjuran has quit [Read error: Connection reset by peer]
<dh`>
quicksort isn't, so it takes more than 10x longer
<mrvn>
dh`: No, it's O(n * w)
<mrvn>
in your one example w is constant but not always.
<dh`>
yes, and the width is the same in both cases here
<dh`>
now, if I go to sort 1000 16-bit shorts, that takes more passes (or more space, but we'll ignore that)
<mrvn>
dh`: you're still missing the point that your solution has O(w) space and O(n * w) time.
jjuran has joined #osdev
<dh`>
I don't care if it has O(w) space because w is a constant.
<dh`>
That's the point.
<dh`>
It is not a function of the input array length.
<mrvn>
Except it isn't. I specifically state the problem without bounds.
<dh`>
it is, because neither real nor theoretical computational devices scale their word size like you're proposing.
<dh`>
to be specific, w is a property of my code, not of the input.
<dh`>
(and it's not itself fixed either, for sorting 8-bit bytes with radix sort it's quite reasonable to code it as a single pass, but it's also quite reasonable to code it as two, depending on other implementation tradeoffs.)
doug16k has joined #osdev
<dh`>
the reason the w is important is if you're sorting non-fixed-length values like strings
<dh`>
you can sort text input by doing 80 passes, but it does kinda suck that way.
<dh`>
if we take your problem on strings instead of integers, it becomes a whole different ballgame
<dh`>
and then my guess is it's not possible
<mrvn>
unless it's strings containing the binary representation of numbers <= n
blockhead has joined #osdev
<dh`>
strings for which you have a perfect hash that maps them to the integers 0..k :-)
bauen1 has joined #osdev
<dh`>
anyway I think this has reached the chop-logic stage
<dh`>
sorry, I'm in a bad mood today apparently
<dh`>
not really appropriate of me to have been taking it out on you
<moon-child>
mrvn: you also have O(w) space
<moon-child>
because you have 3 w-bit integers
<mrvn>
moon-child: dh has 256 * w w-bit integers.
<dh`>
well, 256 * w/8, could also be 16 * w/4, 4 * w/2, or 2 * w
<dh`>
mrvn's solution is the 2 * w form, don't immediately see why you'd need 3
<dh`>
anyway either way it's O(w) space
<dh`>
no, wait, that's not right
<zid`>
My face is O(n) space
<dh`>
oh, right, my solution didn't mod by 3.
<dh`>
so I had 256 * w/8 w-bit integers but it could be 256 * w/8 2-bit integers
<dh`>
and going by bits instead of bytes it becomes 2 * w 2-bit integers, taking advantage of it being just 0 and 1 reduces that to w 2-bit integers, and taking the transpose makes it 2 w-bit integers
<dh`>
but since w is a constant it all disappears
<dh`>
and if w isn't a constant, it doesn't work :-)
noeontheend has joined #osdev
dude12312414 has quit [Quit: THE RAM IS TOO DAMN HIGH]
Celelibi has quit [Ping timeout: 276 seconds]
terminalpusher has quit [Remote host closed the connection]
\Test_User has quit [Quit: e]
ebrasca has quit [Ping timeout: 255 seconds]
Vercas has quit [Remote host closed the connection]
heat has quit [Remote host closed the connection]
gildasio1 has quit [Ping timeout: 268 seconds]
pretty_d1 has quit [Quit: WeeChat 3.5]
Celelibi has joined #osdev
ripmalware has joined #osdev
zaquest has quit [Remote host closed the connection]