24 ms·

I'll try to answer these, just for fun, even though I am not doing an interview. I have not Googled anything, so if things are horribly wrong, let me know. - I

by rcconf 6y ago

I'll try to answer these, just for fun, even though I am not doing an interview. I have not Googled anything, so if things are horribly wrong, let me know. - I have no idea, but I could try answering this through thinking through the problem. Generally a linked list has a pointer to from one item to the other. An array list I assume uses arrays for holding the items using indexes. What are the available operations generally for a data structure? Search - Search would be O(1) in array list and O(N) in linked list, can't be this. Insert - Insert in a linked list is actually quite quick if you have the node since you could just move the pointers. For an array list, you would have to shift everything over. I think this is the answer. Remove - Same deal as Insert. Did I get this right? - Because processes cannot access each others memory, the OS prevents from happening. A pointer is a pointer to an address in memory so you generally cannot do this. In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs? - Neither, it's pass by copy from what I recall. Or something of the sorts. Maybe call by sharing? I would just explain how it works since that's easier, generally everything in Java is copied, so it's pass by value in the traditional sense. But when you think pass by value, are objects copied? The answer is no, objects copy their pointer instead in Java. So when you modify a passed object, it does modify the underlying data in that object, but you can never re-assign the object. - Nope, I don't think so. From what I recall, I've always had programs fail to run if I use the same IP + Port + Interface. You can do virtual hosts in Apache/Nginx tho where you can handle multiple different domains on the same port. - Volatile is generally used when working with threading. I cannot fully recall what it is, but it's required in thread safety. I would generally use thread safety operations and data structures instead here, but I do recall having to use volatile a few times. - I don't know how a breakpoint works exactly, but it's a marker placed in code and when a debugger runs into it, it stops the process. I assume since the Java code gets converted to byte code for the JVM to process, it would be a byte code added between the lines where the breakpoint lives. Note: haven't used Java in 4 years.

fiddlerwoaroof 6y ago
I don’t know if this is true for linked-lists/arrays: but it is sometimes true that an O(1) algorithm is slower than an O(n) one, for small ns (hash-table vs. a linear search of a list of pairs is one example of this). For almost all of these questions I’d be concerned about unusual edge cases: like, I believe it’s possible for two processes to share the same IP/Port on Linux, if you set the right socket options.
- fiddlerwoaroof 6y ago
  Yeah, I think SO_REUSEPORT allows that: https://superuser.com/a/1267230 https://superuser.com/a/1267230
  - lmilcin 6y ago
    Thanks for this one, I forgot about it. This is relatively new addition, in times past the only way was to listen on separate protocols (one process on TCP and one on UDP, for example).
    - SAI_Peregrinus 6y ago
      It's also OS (well, network stack) dependent. The most general answer is that it's possible, but you might need a custom network stack to do it.
marcosdumay 6y ago
> In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs? Modern OSes all have shared memory functionality. And dynamically linked libs are a complicated thing, so it's both yes and no there, at least on some OSes, while on others it's a clear no :) > Neither, it's pass by copy from what I recall. Pass by copy is the same thing as pass by value. In C and Pascal the definitions are pretty clear, but people insist on using them on other languages where they don't make sense. Let's extend it a bit: is Haskell a pass by value or pass by reference language? What about Prolog? About breakpoints, they usually have hardware support. But since Java runs on a virtual machine, I have no idea it the buck stops at the JVM or if they use the hardware interface.
- lmilcin 6y ago
  Yes, the value can either be copied or a reference to it can be passed and this determines whether it is pass by value or by reference. It is clear that Java is pass by value but a little bit confusing since everybody is used to thinking about objects as references and this people confuse that these are different references than the ones in "pass by reference". As to breakpoints this is more complicated and will depend on whether the code is interpreted or it has already been compiled. In an interpreted bytecode (before JIT comes and compiles it) the buck stops at JVM as it is the one responsible for actually executing the bytecode. Once JIT comes and compiles the code, the JVM looses ability to stop at a given physical instruction. In this case I think one of two things happen: 1. The function reverts to interpreted (bytecode) version. or, 2. The JVM inserts instruction into the generated bytecode. But I don't know JVM that well to tell which one is used, actually.
lmilcin 6y ago
1. So, Linked Lists vs Arrays is tough and situation specific. What I look from candidate is general understanding of the problem instead of just blindly saying "linked lists are faster for insertions and deletions". Believe or not, ArrayList are faster for most real life examples (or can be made much faster). Basically (not very precisely but describes it pretty well), for Linked List to be faster than Array List you need an index (or some other way to locate an entry like when you iterate over the list and already have the reference) or perform most operations at both ends. Against popular knowledge, ArrayList is faster in any random access (read, insert or delete) requiring first linear search to locate the entry or insertion place. Why writes is faster even if you have to move heaps of memory to insert something in the middle of array is because searches are so much more expensive for Linked List. Linear search through unindexed Linked List is horribly inefficient compared to ArrayList for many reasons. First, the data is less dense due to references. Then to access next element you need to read pointer from memory and dereference it and this is rather expensive compared to incrementing a pointer which is what you get to get to next element in array list. Then if you have large data structure that was result of random writes it will have rather random layout in memory in case of linked list meaning you will be jumping all over memory and not making good use of prefetching or sharing cache lines. Having CPU prefetch next pages as you iterate through the ArrayList is incredible speedup (but you can get linked list arranged roughly the same way in memory but it can be complex). Then the fact that it is easy to parallellize linear search on array list but not possible on linked list. If the array list can be kept sorted you can do other search strategies (like binary search) but that doesn't work with linked list. The list is long. Linked list will be faster if you require insertions and deletions to be fast AT BOTH ends. If you need to insert at the beginning of the ArrayList but not at the end, just reverse the order. It is possible that you can iterate over the list and do operations on elements (for example, delete it). You use the fact that you already have the reference to the location in in that case Linked List may be much faster than Array List. 2. Virtual Memory. Because each process has their own memory translations. Basically, userspace pointer does not point to physical memory directly. Instead, every process has their own namespace and same pointer values have different meaning in different namespaces. Those namespaces are then dynamically mapped to physical memory and the Operating System is responsible for keeping the mapping and constantly feeding it to CPU whenever CPU executes userspace code and finds a pointer for which it does not have mapping. CPU keeps Page Table and a buffer of mappings (it is called TLB -- translation lookaside buffer, you may have heard the name). When it gets a pointer to map to physical memory it looks at the page table, when it can't find in page table it refers to lookaside buffer and if it can't find the information necessary it momentarily interrupts to the operating system. This is normally completely invisible to the program unless somebody is doing some microbenchmarking and then can see it as unexplained artifacts and cause some chuckles from people who really know the stuff. It is possible to map region of same physical memory or file to the same userspace range of addresses (for example using mmap or when using shared libraries). In this case it is possible to make multiple processes have pointers with same values to dereference to same physical memory address. Old operating systems that did not have concept of virtual memory were basically open world where a process could access everything. Then the concept of Virtual Memory was introduced but the separation was not enforced in other way because just the fact that single page of physical memory was only mapped from single memory space made it pretty good enforcement (at the time). 3. Java is exclusively pass by value. The values are primitives or references. It is pass by value because the variable in Java holds either a primitive or a reference and when a function is invoked, instead of passing reference to the variable, the value of the variable is copied. Meaning if you have Object a = x; function_call(a); then you are sure than nothing that happened in function_call(a) could modify the variable a. In pass by reference language the the function_call(a) would pass reference to a and this could allow function_call(a) to modify the variable a. 4. You can have multiple programs listening on different protocols. For example, you can have one program listening on TCP port and another on UDP. There is I think some new facility in Linux that allow even more functionality but I am not up to date with it. 5. Volatile ensures ordering of operations around reads writes to the volatile variable is not changed by VM or CPU and also ensures that any writes and reads are directed to main memory (at least on systems with more than one L3 cache, ie. with more than one CPU). On most CPUs this happens by a special fence instruction. I am not very familiar with JVM internals so I don't know how this is exactly done (but I expect special instruction, too). 6. Breakpoint is an instruction that is inserted by the debugger directly into machine code of the running program (bytecode in case of Java program). In case of native program this instruction causes an interrupt that causes CPU to stop the program and wake up Operating System. The operating system then passes control to the debugger (which had to first make appropriate setup for this to happen) and then debugger decides what to do depending on the action debugger user wanted to execute. The way the instruction is inserted is usually interesting by itself. Depending on environment, either some space is kept in the function so that it can grow to accommodate the new instruction or the code of the function is copied somewher else with the new instruction and all references to the function are mapped to point to the new copy of the function machine code. I don't know how this is exactly achieved in Java.

by rcconf 6y ago

fiddlerwoaroof 6y ago

I don’t know if this is true for linked-lists/arrays: but it is sometimes true that an O(1) algorithm is slower than an O(n) one, for small ns (hash-table vs. a linear search of a list of pairs is one example of this). For almost all of these questions I’d be concerned about unusual edge cases: like, I believe it’s possible for two processes to share the same IP/Port on Linux, if you set the right socket options.

fiddlerwoaroof 6y ago
Yeah, I think SO_REUSEPORT allows that: https://superuser.com/a/1267230 https://superuser.com/a/1267230
- lmilcin 6y ago
  Thanks for this one, I forgot about it. This is relatively new addition, in times past the only way was to listen on separate protocols (one process on TCP and one on UDP, for example).
  - SAI_Peregrinus 6y ago
    It's also OS (well, network stack) dependent. The most general answer is that it's possible, but you might need a custom network stack to do it.

marcosdumay 6y ago

> In terms of where would this work, umm, maybe in an old OS that didn't have the protection, or perhaps dynamically linking libs? Modern OSes all have shared memory functionality. And dynamically linked libs are a complicated thing, so it's both yes and no there, at least on some OSes, while on others it's a clear no :) > Neither, it's pass by copy from what I recall. Pass by copy is the same thing as pass by value. In C and Pascal the definitions are pretty clear, but people insist on using them on other languages where they don't make sense. Let's extend it a bit: is Haskell a pass by value or pass by reference language? What about Prolog? About breakpoints, they usually have hardware support. But since Java runs on a virtual machine, I have no idea it the buck stops at the JVM or if they use the hardware interface.

lmilcin 6y ago
Yes, the value can either be copied or a reference to it can be passed and this determines whether it is pass by value or by reference. It is clear that Java is pass by value but a little bit confusing since everybody is used to thinking about objects as references and this people confuse that these are different references than the ones in "pass by reference". As to breakpoints this is more complicated and will depend on whether the code is interpreted or it has already been compiled. In an interpreted bytecode (before JIT comes and compiles it) the buck stops at JVM as it is the one responsible for actually executing the bytecode. Once JIT comes and compiles the code, the JVM looses ability to stop at a given physical instruction. In this case I think one of two things happen: 1. The function reverts to interpreted (bytecode) version. or, 2. The JVM inserts instruction into the generated bytecode. But I don't know JVM that well to tell which one is used, actually.

lmilcin 6y ago

1. So, Linked Lists vs Arrays is tough and situation specific. What I look from candidate is general understanding of the problem instead of just blindly saying "linked lists are faster for insertions and deletions". Believe or not, ArrayList are faster for most real life examples (or can be made much faster). Basically (not very precisely but describes it pretty well), for Linked List to be faster than Array List you need an index (or some other way to locate an entry like when you iterate over the list and already have the reference) or perform most operations at both ends. Against popular knowledge, ArrayList is faster in any random access (read, insert or delete) requiring first linear search to locate the entry or insertion place. Why writes is faster even if you have to move heaps of memory to insert something in the middle of array is because searches are so much more expensive for Linked List. Linear search through unindexed Linked List is horribly inefficient compared to ArrayList for many reasons. First, the data is less dense due to references. Then to access next element you need to read pointer from memory and dereference it and this is rather expensive compared to incrementing a pointer which is what you get to get to next element in array list. Then if you have large data structure that was result of random writes it will have rather random layout in memory in case of linked list meaning you will be jumping all over memory and not making good use of prefetching or sharing cache lines. Having CPU prefetch next pages as you iterate through the ArrayList is incredible speedup (but you can get linked list arranged roughly the same way in memory but it can be complex). Then the fact that it is easy to parallellize linear search on array list but not possible on linked list. If the array list can be kept sorted you can do other search strategies (like binary search) but that doesn't work with linked list. The list is long. Linked list will be faster if you require insertions and deletions to be fast AT BOTH ends. If you need to insert at the beginning of the ArrayList but not at the end, just reverse the order. It is possible that you can iterate over the list and do operations on elements (for example, delete it). You use the fact that you already have the reference to the location in in that case Linked List may be much faster than Array List. 2. Virtual Memory. Because each process has their own memory translations. Basically, userspace pointer does not point to physical memory directly. Instead, every process has their own namespace and same pointer values have different meaning in different namespaces. Those namespaces are then dynamically mapped to physical memory and the Operating System is responsible for keeping the mapping and constantly feeding it to CPU whenever CPU executes userspace code and finds a pointer for which it does not have mapping. CPU keeps Page Table and a buffer of mappings (it is called TLB -- translation lookaside buffer, you may have heard the name). When it gets a pointer to map to physical memory it looks at the page table, when it can't find in page table it refers to lookaside buffer and if it can't find the information necessary it momentarily interrupts to the operating system. This is normally completely invisible to the program unless somebody is doing some microbenchmarking and then can see it as unexplained artifacts and cause some chuckles from people who really know the stuff. It is possible to map region of same physical memory or file to the same userspace range of addresses (for example using mmap or when using shared libraries). In this case it is possible to make multiple processes have pointers with same values to dereference to same physical memory address. Old operating systems that did not have concept of virtual memory were basically open world where a process could access everything. Then the concept of Virtual Memory was introduced but the separation was not enforced in other way because just the fact that single page of physical memory was only mapped from single memory space made it pretty good enforcement (at the time). 3. Java is exclusively pass by value. The values are primitives or references. It is pass by value because the variable in Java holds either a primitive or a reference and when a function is invoked, instead of passing reference to the variable, the value of the variable is copied. Meaning if you have Object a = x; function_call(a); then you are sure than nothing that happened in function_call(a) could modify the variable a. In pass by reference language the the function_call(a) would pass reference to a and this could allow function_call(a) to modify the variable a. 4. You can have multiple programs listening on different protocols. For example, you can have one program listening on TCP port and another on UDP. There is I think some new facility in Linux that allow even more functionality but I am not up to date with it. 5. Volatile ensures ordering of operations around reads writes to the volatile variable is not changed by VM or CPU and also ensures that any writes and reads are directed to main memory (at least on systems with more than one L3 cache, ie. with more than one CPU). On most CPUs this happens by a special fence instruction. I am not very familiar with JVM internals so I don't know how this is exactly done (but I expect special instruction, too). 6. Breakpoint is an instruction that is inserted by the debugger directly into machine code of the running program (bytecode in case of Java program). In case of native program this instruction causes an interrupt that causes CPU to stop the program and wake up Operating System. The operating system then passes control to the debugger (which had to first make appropriate setup for this to happen) and then debugger decides what to do depending on the action debugger user wanted to execute. The way the instruction is inserted is usually interesting by itself. Depending on environment, either some space is kept in the function so that it can grow to accommodate the new instruction or the code of the function is copied somewher else with the new instruction and all references to the function are mapped to point to the new copy of the function machine code. I don't know how this is exactly achieved in Java.